<动态规划定义>（是竞赛中最常见，最难理解的问题）

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

动态规划是不断决策求最优解的过程

<动态规划的类型>

<如何分析动态规划>

<DP经典问题>&0-1背包问题&动态规划<Acwing

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

<解题方法>

二维数组，动态转移方程。

（1）状态f[i][j]定义：前 i个物品，背包容量 j下的最优解（最大价值）： 当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i件物品的决策，状态f[i][j]不断由之前的状态更新而来

（2）当前背包容量不够（j < v[i]），没得选，因此前 i个物品最优解即为前 i−1个物品最优解：对应代码：f[i][j] = f[i - 1][j]。

（3）当前背包容量够，可以选，因此需要决策选与不选第 i个物品： 选：f[i][j] = f[i - 1][j - v[i]] + w[i]。 不选：f[i][j] = f[i - 1][j] 。 我们的决策是如何取到最大价值，因此以上两种情况取 max() 。

<代码实现>

  import java.util.Scanner;
  public class Main {
public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int n= input.nextInt();
    int m= input.nextInt();
    int [][]f=new int[1010][1010];
    int []v=new int[1010];
    int []w=new int[1010];
    for(int i=1;i<=n;i++)
    {
        v[i]= input.nextInt();
        w[i]= input.nextInt();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            {
                f[i][j]=Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);//动态转移方程
            }
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)
    {
        res=Math.max(res,f[n][i]);
    }
    System.out.println(res);

}
}

alt