本文共 10555 字，大约阅读时间需要 35 分钟。

动态规划

1. 动态规划特点，一个模型三个特征

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

• 最优子结构
• 无后效性
  无后效性从字面上意思可以理解为：一旦一个阶段的结果计算出来，后面阶段的求解过程不会影响前面阶段的计算结果。
• 重复子问题

2. 背包问题

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

我们把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量），也就是例子中的 9。于是，我们就成功避免了每层状态个数的指数级增长。我们用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。我们用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。我把整个计算的过程画了出来，你可以看看。图中 0 表示 false，1 表示 true。我们只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。

weight:物品重量，n:物品个数，w:背包可承载重量public int knapsack(int[] weight, int n, int w) {
     boolean[][] states = new boolean[n][w+1]; // 默认值false  states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化  if (weight[0] <= w) {
       states[0][weight[0]] = true;  }  for (int i = 1; i < n; ++i) {
    // 动态规划状态转移    for (int j = 0; j <= w; ++j) {
   // 不把第i个物品放入背包      if (states[i-1][j] == true) states[i][j] = states[i-1][j];    }    for (int j = 0; j <= w-weight[i]; ++j) {
   //把第i个物品放入背包      if (states[i-1][j]==true) states[i][j+weight[i]] = true;    }  }  for (int i = w; i >= 0; --i) {
    // 输出结果    if (states[n-1][i] == true) return i;  }  return 0;}

实际上，这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

时间复杂度为O(nw)

public static int knapsack2(int[] items, int n, int w) {
     boolean[] states = new boolean[w+1]; // 默认值false  states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化  if (items[0] <= w) {
       states[items[0]] = true;  }  for (int i = 1; i < n; ++i) {
    // 动态规划    for (int j = w-items[i]; j >= 0; --j) {
   //把第i个物品放入背包      if (states[j]==true) states[j+items[i]] = true;    }  }  for (int i = w; i >= 0; --i) {
    // 输出结果    if (states[i] == true) return i;  }  return 0;}

3. 背包问题升级

在递归树中，每个节点表示一个状态。现在我们需要 3 个变量（i, cw, cv）来表示一个状态。其中，i 表示即将要决策第 i 个物品是否装入背包，cw 表示当前背包中物品的总重量，cv 表示当前背包中物品的总价值。

private int maxV = Integer.MIN_VALUE; // 结果放到maxV中private int[] items = {
   2，2，4，6，3};  // 物品的重量private int[] value = {
   3，4，8，9，6}; // 物品的价值private int n = 5; // 物品个数private int w = 9; // 背包承受的最大重量public void f(int i, int cw, int cv) {
    // 调用f(0, 0, 0)  if (cw == w || i == n) {
    // cw==w表示装满了，i==n表示物品都考察完了    if (cv > maxV) maxV = cv;    return;  }  f(i+1, cw, cv); // 选择不装第i个物品  if (cw + weight[i] <= w) {
       f(i+1,cw+weight[i], cv+value[i]); // 选择装第i个物品  }}

在递归树中，有几个节点的 i 和 cw 是完全相同的，比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，我们可以舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。也就是说，对于 (i, cw) 相同的不同状态，那我们只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑

public static int knapsack3(int[] weight, int[] value, int n, int w) {
     int[][] states = new int[n][w+1];  for (int i = 0; i < n; ++i) {
    // 初始化states    for (int j = 0; j < w+1; ++j) {
         states[i][j] = -1;    }  }  states[0][0] = 0;  if (weight[0] <= w) {
       states[0][weight[0]] = value[0];  }  for (int i = 1; i < n; ++i) {
    //动态规划，状态转移    for (int j = 0; j <= w; ++j) {
    // 不选择第i个物品      if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];    }    for (int j = 0; j <= w-weight[i]; ++j) {
    // 选择第i个物品      if (states[i-1][j] >= 0) {
           int v = states[i-1][j] + value[i];        if (v > states[i][j+weight[i]]) {
             states[i][j+weight[i]] = v;        }      }    }  }  // 找出最大值  int maxvalue = -1;  for (int j = 0; j <= w; ++j) {
       if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];  }  return maxvalue;}

4.状态转移表

我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。

5.状态转移方程

状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程，那动态规划问题基本上就解决一大半了，而翻译成代码非常简单。但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到。

6. 题目

1. 最大子序和
   链接：https://leetcode-cn.com/problems/maximum-subarray/
   
   贪心算法：

class Solution {
   public:    int maxSubArray(vector
   
    & nums)     {
           int len = nums.size();        int sum = 0;        int max = nums[0];        int i = 0;        while(i < len)        {
                if(sum >= 0)            {
                                   sum += nums[i];                ++i;                if(sum > max)                {
                       max = sum;                }            }            else            {
                   sum = 0;            }        }        return max;    }};//思路为：//直接做单层遍历，用sum保存从头加的和，当sum小于0时，清零重新累加，在过程中记下sum的最大值
   

使用dp算法：

// 思考状态：dp[i]代表着以nums[i]结尾的最大的子序列和。// 思考状态转移方程：dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); 取dp[i-1]+nums[i]和nums[i]的最大值是因为考虑dp[i-1]是否对nums[i]产生了负增益，如果对nums[i]产生了负增益，那么不如不产生，对应的就是将dp[i-1]去掉。// 思考初始化：dp[0] = nums[0]，所以i必须从1开始直到末尾。// 思考输出：输出dp数组的最大值即可。class Solution {
       public int maxSubArray(int[] nums) {
           int len = nums.length;        int[] dp = new int[len];        dp[0] = nums[0];        int res = Integer.MIN_VALUE;        for(int i = 1; i < len; i++){
               dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);            if(dp[i] > res){
                   res = dp[i];            }        }        return Math.max(dp[0], res);    }}

这两种方法实现不一样，其实想法是相同的

2. 最小路径和
   链接：https://leetcode-cn.com/problems/minimum-path-sum/
   

// 思路: 基础的dp思想// 迁移方程：dp[i][j] = Math.min((dp[i-1][j] + grid[i][j]), (dp[i][j-1] + grid[i][j]));class Solution {
       public int minPathSum(int[][] grid) {
           if(grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1){
               return 0;        }        int row = grid.length, col = grid[0].length;        int dp[][] = new int[row][col];        // 初始化        dp[0][0] = grid[0][0];        for(int i = 1; i < row; i++){
               dp[i][0] = dp[i-1][0] + grid[i][0];        }        for(int i = 1; i < col; i++){
               dp[0][i] = dp[0][i-1] + grid[0][i];        }        for(int i = 1; i < row; i++){
               for(int j = 1; j < col; j++){
                   dp[i][j] = Math.min((dp[i-1][j] + grid[i][j]), (dp[i][j-1] + grid[i][j]));            }        }        return dp[row-1][col-1];    }}

3. 不同路径
   链接：https://leetcode-cn.com/problems/unique-paths/
   

// 迁移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1];class Solution {
       public int uniquePaths(int m, int n) {
           int[][] dp = new int[m][n];        // 初始化        for(int i = 0; i < m; i++){
               dp[i][0] = 1;        }        for(int i = 0; i < n; i++){
               dp[0][i]= 1;        }        for(int i = 1; i < m; i++){
               for(int j = 1; j < n; j++){
                   dp[i][j] = dp[i-1][j] + dp[i][j-1];            }        }        return dp[m-1][n-1];    }}

4. 不同路径2
   链接：https://leetcode-cn.com/problems/unique-paths-ii/
   

// 思路： dp[i][j] // 状态转移方程：  当obstacleGrid[i][j] == 1 时 dp[i][j] = 0 ,//               当obstacleGrid[i][j] == 0 时 dp[i][j] = dp[i-1][j] + dp[i][j-1];class Solution {
       public int uniquePathsWithObstacles(int[][] obstacleGrid) {
           int row = obstacleGrid.length;        int col = obstacleGrid[0].length;        // 定义dp，初始化        int[][] dp = new int[row][col];        int frow = 1;        for(int i = 0; i < row; i++){
               if(obstacleGrid[i][0] == 1){
                   frow = 0;            }            dp[i][0] = frow;        }        int fcol = 1;        for(int i = 0; i < col; i++){
               if(obstacleGrid[0][i] == 1){
                   fcol = 0;            }            dp[0][i] = fcol;        }        for(int i = 1; i < row; i++){
               for(int j = 1; j < col; j++){
                   if(obstacleGrid[i][j] == 1){
                       dp[i][j] = 0;                }else{
                       dp[i][j] = dp[i-1][j] + dp[i][j-1];                }            }        }        return dp[row-1][col-1];    }}

5. 爬楼梯
   链接： https://leetcode-cn.com/problems/climbing-stairs/
   

// 思路：dp[i] 为到达i阶的方法数，到达i前只有两种方法，从i-1走一阶，从i-2走两阶// 迁移方程：dp[i] = dp[i-1] + dp[i-2]class Solution {
       public int climbStairs(int n) {
           if(n == 1 || n == 2){
               return n;        }        int[] dp = new int[n];        // 初始化        dp[0] = 1;        dp[1] = 2;        for(int i = 2; i < n; i++){
               dp[i] = dp[i-1] + dp[i-2];        }        return dp[n -1];    }}

6. 使用最小花费爬楼梯
   链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs/
   

// 思路： 同爬楼梯，难度在于题目读不懂// 动态迁移方程：dp[i] = Math.min(dp[i-1], dp[i-2])  + cost[i];class Solution {
       public int minCostClimbingStairs(int[] cost) {
           int n = cost.length;        if(n <= 2){
               return 0;        }        int[] dp = new int[n];        dp[0] = cost[0];        dp[1] = cost[1];        for(int i = 2; i < n; i++){
                   dp[i] = Math.min(dp[i-1], dp[i-2])  + cost[i];        }        return Math.min(dp[n-2], dp[n-1]);    }}

7. 打家劫舍
   链接：https://leetcode-cn.com/problems/house-robber/
   

// 思路：dp[i] 为到达低i间房偷盗的最高金额数// 迁移方程： dp[i] = Max(dp[i-2] + nums[i], dp[i-1])class Solution {
       public int rob(int[] nums) {
           int len = nums.length;        if(len == 0){
               return 0;        }        if(len == 1){
               return nums[0];        }        if(len == 2){
               return Math.max(nums[0], nums[1]);        }        int[] dp = new int[len];        dp[0] = nums[0];        dp[1] = Math.max(nums[0], nums[1]);        for(int i = 2; i < len; i++){
                dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);        }        return dp[len-1];    }}

7. 买卖股票的最佳时机
   链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
   

// 思路： 定义状态 dp[i][0]  dp[i][1]  i表示当前天数， 0 1 表示是否持仓, dp[i][j]表示当前利润// dp[i][0]：规定了今天不持股，有以下两种情况：// 昨天不持股，今天什么都不做；// 昨天持股，今天卖出股票（现金数增加），// dp[i][1]：规定了今天持股，有以下两种情况：// 昨天持股，今天什么都不做（现金数与昨天一样）；// 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。// 状态方程： 当天未持仓时，dp[i][0] = Math.max(dp[i-1][0], dp[i-1][0] + prices[i])//            当天持仓时， dp[i][1] = Math.max(dp[i-1][1], -prices[i])class Solution {
       public int maxProfit(int[] prices) {
           int n = prices.length;                int[][] dp = new int[n][2];        dp[0][0] = 0;        dp[0][1] = -prices[0];        for(int i = 1; i < n; i++){
               dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);        }        return Math.max(dp[n-1][0], dp[n-1][1]);    }}

转载地址：http://htjwi.baihongyu.com/