背包

0-1背包：

$\mathbf{注意状态定义f(i,j)表示的是以下集合:\,\,^{1}在前i个物品中选取商品,\,\,^{2}且总重量小于等于j.}$
$\\$
$\mathbf{第二层为什么要从m到v[\,i\,]\,?}$
$问题的关键在于如果是顺序的话,dp\,[\,i-1\,]\,[\,j-v\,[\,i\,]\,]\,是在dp\,[\,i-1\,]\,[\,j\,]\,装填到数组dp\,[\,]\,里的,$
$此时运算在第i层的第j个，那么上一层i-1中,只有从j+1到m还未被第i层更新。$
$dp\,[\,j-v\,[\,i\,]\,]\,已经被覆盖了。$

import java.util.*;

public class Main
{
    static final int N = 1010;
    // static int[][] dp = new int[N][N];
    static int[] dp = new int[N];
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int n,m;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n; i++)
        {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        // for(int i = 1; i <= n; i++)
        // {
        //     for(int j = 0; j <= m; j++)
        //     {
        //         dp[i][j] = dp[i-1][j];
        //         if(j-v[i] >= 0) 
        //             dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
        //     }
        // }
        for(int i = 1; i <= n; i++)
        {
        //j >= 0 && j - v[i] >= 0 -> j >= v[i]
            for(int j = m ; j >= v[i]; j--)
            {
                // dp[j] = dp[j];
                // if(j - v[i] >= 0)
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

完全背包

        for(int i = 1; i <= n; i++)
        {
            for(int j = v[i]; j <= m; j++)
            {
                dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }

多重背包

import java.util.*;

public class Main
{
    static int n,m;
    static final int N = 12000;     //N*logS
    static int[] dp = new int[N];
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            int vv = sc.nextInt();
            int ww = sc.nextInt();
            int s = sc.nextInt();
            int k = 1;
            while(k <= s)
            {
                cnt++;
                v[cnt] = vv * k;
                w[cnt] = ww * k;
                s -= k;
                k *= 2;
            }
            if(s > 0)
            {
                cnt++;
                v[cnt] = vv * s;
                w[cnt] = ww * s;
            }
        }
        n = cnt;
        for(int i = 1; i <= n; i++)
        {
            for(int j = m; j >= v[i]; j--)
            {
                dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

分组背包

$\mathbf{关于dp\,[\,]\,[\,]\,的dp\,[\,i\,]\,[\,j\,]\, = dp\,[\,i-1\,]\,[\,j\,]\,:}$
$一定要在3-th\,for循环之外,因为它表示的是上一层的结果$
$也就是从前i-1组中选择,如果它在3-th\,for循环之内,$
$就表示每次把第i层的最后一个k-th选择方案和前i-1组的最优方案比较,$
$丢失了i-1 层的:[1,k-1]个方案的比较$

import java.util.*;

public class Main
{
    static int n,m;
    static final int N = 110;
    static int[] dp = new int[N];
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[] s = new int[N];

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1; i <= n; i++)
        {
            s[i] = sc.nextInt();
            for(int j = 1; j <= s[i]; j++)
            {
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }

        //dp[][]
        /*
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= m; j++)
            {
                dp[i][j] = dp[i-1][j];          //!!!!

                for(int k = 1; k <= s[i]; k++)
                {
                    if(j >= v[i][k])
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - v[i][k]] + w[i][k]);
                }
            }
        }
        */

        //dp[]
        for(int i = 1; i <= n; i++)
            for(int j = m; j >= 0; j--)
                for(int k = 1; k <= s[i]; k++)
                    if(j >= v[i][k])
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);

        System.out.println(dp[m]);
    }
}

线性DP

数字三角形

$\mathbf{f(i,j)\,表示的是中止坐标为\,(i,j)\,的集合}$
$\mathbf{dp\,[\,i\,]\,[\,j\,]\, = max(dp\,[\,i+1\,]\,[\,j\,],\,dp\,[\,i+1\,]\,[\,j+1\,]\,) + value\,[\,i\,]\,[\,j]}$

        for(int i = n; i >= 1; i--)
        {
            for(int j = 1; j <= i; j++)
            {
                dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j+1]) +g[i][j];
            }
        }

最长公共子序列

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if(a[i] == b[i]) 
    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);

区间Dp

$\mathbf{^{1}先枚举区间长度\,\,^{2}再枚举区间左端点}$
$\mathbf{f(i,j)\,表示的是区间\,[\,i,j\,]\,的方案集合}$

        for(int len = 2; len <= n ; len++)          //枚举区间长度
        {
            for(int i = 1; i + len - 1 <= n; i++)   //枚举左端点
            {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = i; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }