刷题笔记之动态规划(一)

动态规划五部曲

• 以LeetCode 509. 斐波那契数为例：

确定dp数组以及下标的含义

dp[i]: 第i个数的斐波那契数是dp[i]

确定递推公式

斐波那契数列的特点就是后一个数的值等于前两个数相加,所以不难推出：
dp[i] = dp[i - 1] + dp[i - 2];

dp数组初始化

这一步和确定dp数组以及下标的含义，翻译即可:

dp[0] = 0;//第0个数的斐波那契数是0
dp[1] = 1;//第1个数的斐波那契数是1

确定遍历顺序

由于斐波那契数的后一个数是由前两个数相加而来，故应该从前往后遍历
而且由状态转移式 dp[i] = dp[i - 1] + dp[i - 2]; 可以看出，dp[i]依赖 dp[i - 1] 和 dp[i - 2]

打印dp数组

当i = 10 时，dp数组的结果应该是：
0 1 1 2 3 5 8 13 21 34 55
如果出现结果不符合预期的情况，就要检查递推公式或遍历顺序是否符合逻辑。

• 完整代码

  class Solution {
      public int fib(int n) {
          if (n == 1 || n == 2) {
              return 1;
          }
          if (n == 0) {
              return 0;
          }
          int dp = 0;//因为只需要记录最终结果，可以把dp数组优化成一个数
          int f1 = 0;
          int f2 = 1;
          for (int i = 2; i <= n; i++) {
              dp = f1 + f2;
              f1 = f2;
              f2 = dp;
          }
          return dp;
      }
  }

小试牛刀

LeetCode 509. 斐波那契数

LeetCode题目链接

LeetCode 70. 爬楼梯

LeetCode题目链接
动态规划五部曲：

• 确定dp数组以及下标的含义
  dp[i]: 爬到第 i 层有 dp[i] 种方法

• 确定递推公式
  以 i = 3 为例，有三种情况：
  1.一次只爬一层，爬三次上来；
  2.先爬一层，再爬两层上来；
  3.先爬两层，再爬一层上来；
  第二种和第三种情况没有本质上的区别，只是先后顺序不同。不难推出：
  dp[i] = dp[i - 1] + dp[i - 2]

• dp数组初始化

  dp[1] = 1;//爬到第 1 层有 1 种方法
  dp[2] = 2;//爬到第 2 层有 2 种方法

  为什么不初始化dp[0]?
  1.题目提示 1 <= n <= 45 ，定义dp[0]本就没有意义。
  2.有歧义，我直接站着不动到达顶层也可以算一种方法，但按照我给dp数组的定义又是0种方法。

• 确定遍历顺序
  显然我不能倒着爬，这不符合常理，且由递推公式可知，本题是从前往后遍历。

  for(int i = 3; i <= n; i++){
      dp[i] = dp[i - 1] + dp[i - 2];
  }

• 打印dp数组
  当i = 10 时，dp数组的结果应该是：
  0 1 1 2 3 5 8 13 21 34 55
  其实这就是斐波那契数列。

• 完整代码

  class Solution {
      public int climbStairs(int n) {
          int[] dp = new int[n + 1];
          if (n <= 1) {
              return n;
          }
          dp[1] = 1;
          dp[2] = 2;
          for (int i = 3; i <= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];
          }
          return dp[n];
      }
  }

LeetCode 746. 使用最小花费爬楼梯

LeetCode题目链接

动态规划五部曲：

• 确定dp数组以及下标的含义
  dp[i] : 爬到第 i 层 的最小花费为 dp[i]

• 确定递推公式
  要到达第 i 层，要么爬 i - 1层往上爬，要么从i - 2层往上爬，其实本题与509. 斐波那契数和70. 爬楼梯很像，唯一的区别在于它多了**每向上爬一层或两层的花费cost[i]**，而我们对dp数组的定义又是爬到第 i 层 的最小花费为 dp[i]，所以不要忘了把每次向上爬的cost[i]加上再从中取最小值：
  dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

• dp数组初始化

  //注意：站在第0或第1层并不花费，只有向上爬的操作才更新费用
  dp[0] = 0;//爬到第 0 层 的最小花费为 0;
  dp[1] = 0;//爬到第 1 层 的最小花费为 0;

• 确定遍历顺序
  因为是模拟台阶，而且递推公式dp[i]是由dp[i - 1]和dp[i - 2]推出，所以是从前往后遍历。

  for(int i = 2; i <= cost.length; i++){
      dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
  }

• 打印dp数组
  cost = [1,100,1,1,1,100,1,1,100,1],结果为：
  1 2 2 3 3 4 4 5 6

• 完整代码

  class Solution {
      //dp[i]:走到i的位置花费的米
      public int minCostClimbingStairs(int[] cost) {
          int[] dp = new int[cost.length + 1];
          //到达0和1的位置不花费
          dp[0] = 0;
          dp[1] = 0;
          for (int i = 2; i <= cost.length; i++) {
              dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
              System.out.println(dp[i] + " ");
          }
          return dp[cost.length];
      }
  }

LeetCode 62. 不同路径

LeetCode题目链接

动态规划五部曲：

• 确定dp数组以及下标的含义
  dp[i][j]: 走到坐标为 (i, j) 的位置共有dp[i][j]种路径

• 确定递推公式
  要走到 (i, j)，要么从(i - 1, j)向右走一步，要么从(i, j - 1)向下走一步，即：
  dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

• dp数组初始化
  因为从起点一直向右走和一直向下走的路径都只有一条，所以把第一行和第一列都初始化为1

  for (int i = 0; i < m; i++) dp[i][0] = 1;
  for (int j = 0; j < n; j++) dp[0][j] = 1;

• 确定遍历顺序
  由递推公式易得，dp[i][j]都是从其上方和左方得来，所以应该从左至右、从上至下遍历。

  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];
      }
  }

• 打印dp数组
  

• 完整代码

  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 j = 0; j < n; j++) {
              dp[0][j] = 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];
      }
  }

LeetCode 63. 不同路径 II

LeetCode题目链接
本题与62. 不同路径唯一的区别是增加了障碍物，假设走到了(i, j)的位置遇到了障碍，那此处就有 0 种路径可走，写成代码就是dp[i][j] = 0。我们只需要处理初始化时遇到障碍的情况即可。

//初始化第一行和第一列的时候有障碍直接退出了，走不到
for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
    dp[i][0] = 1;
}
    for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
    dp[0][j] = 1;
}

其余代码都与62. 不同路径一样。

LeetCode 343. 整数拆分

LeetCode题目链接

动态规划五部曲：

• 确定dp数组以及下标的含义
  dp[i]: 将 i 个数拆分得到的最大乘积为 dp[i]

• 确定递推公式
  假设将 i 拆分成两个数，最大乘积为 j * (i - j)，那把 i 拆成3个，4个等等该怎么得到乘积呢？
  不妨利用我们对dp数组的定义，先拆出一个 j,剩余的 i - j，无论拆成几个数都可以写为dp[i - j]，最大乘积为 j * dp[i - j]；
  将两式组合取最大值得到：
  dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));

• 初始化dp数组
  题目要求至少将 n 拆成两个数，显然拆 0 和 1 无意义，且不符合我们对dp数组的定义，所以直接从dp[2]开始初始化：
  dp[2] = 1;

• 确定遍历顺序
  由递推公式可知，dp[i]依靠dp[i - j]，所以该从前向后遍历。

  for(int i = 3; i <= n; i++){
      for(int j = 1; j <= i / 2; j++){//二分，取近似的数
          dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
      }
  }

• 打印dp数组
  n = 10,dp数组应为：
  2 3 4 4 6 6 8 9

• 完整代码

  class Solution {
      public int integerBreak(int n) {
          //dp[n]:拆分数字n，求最大乘积为dp[n]
          int[] dp = new int[n + 1];
          dp[2] = 1;
          for (int i = 3; i <= n; i++) {
              for (int j = 1; j <= i / 2; j++) {//二分，取近似的数
                  dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
              }
          }
          return dp[n];
      }
  }

LeetCode 96. 不同的二叉搜索树

LeetCode题目链接

动态规划五部曲：

• 确定dp数组以及下标的含义
  dp[i]: 结点值从1到i互不相同的二叉搜索树有dp[i]种

• 确定递推公式
  如图所示，先举出 n = 1 或 n = 2 的情况：
  
  接下来时 n = 3 的情况：
  

• 当1为头结点时，如果将其子节点视为一个整体，那么它和n = 2时的情况一致；

• 当2为头结点时，它左右都只有一个结点，和n = 1时的情况一致(n = 1可以看成头结点左右有两个空结点);

• 当3为头结点时，它的左右布局又和n = 2时的情况一直；
  我们发现可以通过dp[1]和dp[2]推导得到dp[3]：
  dp[3] = 1为头结点搜索树的数量 + 2为头结点搜索树的数量 + 3为头结点搜索树的数量
  1为头结点搜索树的数量 = 左子树有0个元素的搜索树数量 * 右子树有2个元素的搜索树数量。
  2为头结点搜索树的数量 = 左子树有1个元素的搜索树数量 * 右子树有1个元素的搜索树数量。
  3为头结点搜索树的数量 = 左子树有2个元素的搜索树数量 * 右子树有0个元素的搜索树数量。
  即：dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]
  当以 j 为头结点时，dp[i] = dp[以j为头结点左子树节点数量] *dp[以j为头结点右子树节点数量],即：
  dp[i] = dp[j - 1] * dp[i - j];
  为什么左子树结点数量是 j - 1，右子树结点数量是 i - j?
  因为在从1到i二叉搜索树中，比j小的一定在其左子树，比j大的一定在其右子树。
  为什么是dp[j - 1] * dp[i - j]而不是相加？
  假设以j为头结点其左子树有5种情况，右子树有10种情况，那么总的组合应该是5 * 10 而不是 5 + 10。

• dp数组初始化

  dp[0] = 1;//空树也是二叉搜索树
  dp[1] = 1;

• 确定遍历顺序
  从递推公式易得，结点数为为i的状态是由i之前的状态得来，所以应该遍历i里面每一个数作为头节点的情况。

  for(int i = 2; i <= n; i++){
      for(int j = 1; j <= i; j++){
          dp[i] += dp[j - 1] * dp[i - j]; 
      }
  }

• 打印dp数组
  n = 5,结果为：
  1 1 2 5 14 42

• 完整代码

  class Solution {
      public int numTrees(int n) {
          //输入i，求dp[i]中不同二叉树
          int[] dp = new int[n + 1];
          dp[0] = 1;
          dp[1] = 1;
          for (int i = 2; i <= n; i++) {
              for (int j = 1; j <= i; j++) {
                  dp[i] += dp[j - 1] * dp[i - j];
              }
          }
          return dp[n];
      }
  }