LeetCode 动态规划

发布于 2024-01-21 20:47:29 字数 15795 浏览 23 评论 0

递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。

斐波那契数列

1. 爬楼梯

70.假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思路：定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

dp[i] = dp[i - 1] + dp[i - 2]

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

class Solution {
  public int climbStairs(int n) {
    if(n <= 2) return n;

    int pre1 = 1, pre2 = 2;

    int cur = 0;

    for(int i = 2; i < n; i++){
      cur = pre1 + pre2;
      pre1 = pre2;
      pre2 = cur;
    }

    return cur;
  }
}

2. 强盗抢劫

198.你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路：

定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。

由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以

dp[i] = max(dp[i-2]+nums[i], dp[i-1])

class Solution {
  public int rob(int[] nums) {
    
    int pre1 = 0, pre2 = 0;

    int cur = 0;

    for(int i = 0; i < nums.length; i++){
      cur = Math.max(pre1+nums[i], pre2);
      pre1 = pre2;
      pre2 = cur;
    }

    return cur;
  }
}

3. 强盗在环形街区抢劫

213.你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
   偷窃到的最高金额 = 1 + 3 = 4 。

思路：

抢劫的第一家和最后一家不能相邻，则一共有两种方式[1，n - 1], [0，n-2]。

class Solution {
  public int rob(int[] nums) {
    int n = nums.length;
    if(n == 0) return 0;
    if(n == 1) return nums[0];

    return Math.max(robHelper(nums, 1, n-1), robHelper(nums, 0, n-2));
  }

  int robHelper(int[] nums, int start, int end){
    int pre1 = 0, pre2 = 0;

    int cur = 0;
    
    for(int i = start; i <= end; i++){
      cur = Math.max(pre1+nums[i], pre2);
      pre1 = pre2;
      pre2 = cur;
    }

    return cur;
  }
}

4. 信件错排

题目描述：有 N 个信和信封，它们被打乱，求错误装信方式的数量。

定义一个数组 dp 存储错误方式数量，dp[i] 表示前 i 个信和信封的错误方式数量。假设第 i 个信装到第 j 个信封里面，而第 j 个信装到第 k 个信封里面。根据 i 和 k 是否相等，有两种情况：

i==k，交换 i 和 j 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。
i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。

综上所述，错误装信数量方式数量为：

dp[i] = (i-1)*dp[i-2] + (i-1)*dp[i-1]

5. 母牛生产

题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。

第 i 年成熟的牛的数量为：

dp[i] = dp[i-1] + dp[i-3]

矩阵路径

1. 矩阵的最小路径和

64.给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

长度为 m+n，每次只能选择往右或往下，

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

应注意边界，上面为边界时，则上一步不可能为从上面来，左面为边界时同理，都为边界时，其实在起点。

class Solution {
  public int minPathSum(int[][] grid) {
    for(int i = 0; i < grid.length; i++)
      for(int j = 0; j < grid[0].length; j++){
        if(i == 0 && j == 0) continue;
        else if(i == 0) grid[i][j] = grid[i][j] + grid[i][j-1];
        else if(j == 0) grid[i][j] = grid[i][j] + grid[i-1][j];
        else grid[i][j] = grid[i][j] + Math.min(grid[i][j-1], grid[i-1][j]);
      }
    return grid[grid.length - 1][grid[0].length - 1];
  }
}

2. 矩阵的总路径数

62.一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

1、动态规划

dp[i][j] = dp[i-1][j] + dp[i][j-1]

左边界和上边界都为 1

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++){
        if(i == 0 || j == 0) dp[i][j] = 1;
        else dp[i][j] = dp[i-1][j] + dp[i][j-1];
      } 

    return dp[m-1][n-1];
  }
}

2、排列组合

机器人一共要走 m+n-2 步，向下 m-1 步，则有 C(m+n-2,m-1)种排列组合

class Solution {
  public int uniquePaths(int m, int n) {
    int S = m+n-2;
    int D = m-1;
    long result = 1;
    for(int i = 1; i <= D; i++){
      result = result*(S-D+i)/i;
    }
    return (int)result;
  }
}

数组区间

1. 数组区间和

303.给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

思路：

求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。

在 sum 的第一个位置引入了一个虚拟的 0，这个技巧可以避免在 sumRange 函数中进行额外的条件检查。

class NumArray {

  private int[] sums;

  public NumArray(int[] nums) {
    sums = new int[nums.length+1];
    for(int i = 1; i <= nums.length; i++){
      sums[i] = sums[i - 1] + nums[i - 1];
    }

  }
  
  public int sumRange(int i, int j) {
    return sums[j+1] - sums[i];
  }
}

2. 数组中等差递增子区间的个数

413.等差数列划分

数组 A 包含 N 个数，且索引从 0 开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思路：

dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。

当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。

A = [0, 1, 2, 3, 4]

dp[2] = 1
  [0, 1, 2]
dp[3] = dp[2] + 1 = 2
  [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
  [1, 2, 3]   // 新的递增子区间
dp[4] = dp[3] + 1 = 3
  [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
  [1, 2, 3, 4],  // [1, 2, 3] 之后加一个 4
  [2, 3, 4]    // 新的递增子区间

综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。

总数则是 dp 数组累加的结果

class Solution {
  public int numberOfArithmeticSlices(int[] A) {
    int n = A.length;
    if(n < 3) return 0;
    int[] dp = new int[n];
    for(int i = 2; i < n; i++){
      if(A[i] - A[i-1] == A[i-1] - A[i-2]){
        dp[i] = dp[i-1] + 1;
      }
    }
    int total = 0;
    for(int cnt : dp){
      total += cnt;
    }
    return total;
  }
}

分割整数

1. 分割整数的最大乘积

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

class Solution {
  public int integerBreak(int n) {
    int[] dp = new int[n+1];
    dp[1] = 1;
    for(int i = 2; i <= n; i++)
      for(int j = 1; j < i; j++){
        dp[i] = Math.max(dp[i], Math.max(j*dp[i-j], j*(i-j)));
      }
    return dp[n];
  }
}

最长递增子序列

已知一个序列 {S1, S2,...,Sn}，取出若干数组成新的序列 {Si1, Si2,..., Sim}，其中 i1、i2 ... im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个子序列。

如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个递增子序列。

定义一个数组 dp 存储最长递增子序列的长度，dp[n] 表示以 Sn 结尾的序列的最长递增子序列长度。对于一个递增子序列 {Si1, Si2,...,Sim}，如果 im < n 并且 Sim < Sn，此时 {Si1, Si2,..., Sim, Sn} 为一个递增子序列，递增子序列的长度增加 1。满足上述条件的递增子序列中，长度最长的那个递增子序列就是要找的，在长度最长的递增子序列上加上 Sn 就构成了以 Sn 为结尾的最长递增子序列。

 dp[n] = max{ dp[i]+1 | Si < Sn && i < n}

因为在求 dp[n] 时可能无法找到一个满足条件的递增子序列，此时 {Sn} 就构成了递增子序列，需要对前面的求解方程做修改，令 dp[n] 最小为 1，即：

dp[n] = max{ 1, dp[i]+1 | Si < Sn && i < n}

对于一个长度为 N 的序列，最长递增子序列并不一定会以 SN 为结尾，因此 dp[N] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，

max{ dp[i] | 1 <= i <= N}

即为所求。

1.最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

思路：

动态规划。

dp[i]储存当前元素为止最大上升子序列长度，遍历前序 dp，若大于则 dp[j]+1，找出最大值。

class Solution {
  public int lengthOfLIS(int[] nums) {
    if(nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n];
    for(int i = 0; i < n; i++){
      int max = 1;
      for(int j = 0; j < i; j++){
        if(nums[i] > nums[j]){
          max = Math.max(max, dp[j] + 1);
        }
      }
      dp[i] = max;
    }
    int result = 0;
    for(int ret : dp){
      result = Math.max(ret, result);
    }
    return result;
  }
}

最长公共子序列

对于两个子序列 S1 和 S2，找出它们最长的公共子序列。

定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：

当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。

综上，最长公共子序列的状态转移方程为：

对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。

与最长递增子序列相比，最长公共子序列有以下不同点：

针对的是两个序列，求它们的最长公共子序列。
在最长递增子序列中，dp[i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，dp[i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j。
在求最终解时，最长公共子序列中 dp[N][M] 就是最终解，而最长递增子序列中 dp[N] 不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。

1. 最长公共子序列

1143.给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

思路：索引为 0 的行和列表示空串，让边界为 0，即 dp[0][...]，dp[...][0]为 0，初始条件。

class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
      for (int j = 1; j <= n2; j++) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[n1][n2];
  }
}

0-1 背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。
第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w] + v。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)

// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
  int[][] dp = new int[N + 1][W + 1];
  for (int i = 1; i <= N; i++) {
    int w = weights[i - 1], v = values[i - 1];
    for (int j = 1; j <= W; j++) {
      if (j >= w) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[N][W];
}

空间优化

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，

dp[i] = max(dp[j],dp[j-w]+v)

因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w]，防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。

public int knapsack(int W, int N, int[] weights, int[] values) {
  int[] dp = new int[W + 1];
  for (int i = 1; i <= N; i++) {
    int w = weights[i - 1], v = values[i - 1];
    for (int j = W; j >= 1; j--) {
      if (j >= w) {
        dp[j] = Math.max(dp[j], dp[j - w] + v);
      }
    }
  }
  return dp[W];
}

完全背包

完全背包：物品数量为无限个。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。如下例题：

切钢条

给定一段长度为 n 英寸的钢条和一个价格表，求切割方案，使销售收益 Rn 最大。

注：若长度为 n 英寸的钢条的价格 Pn 足够大，最优解可能就是完全不需要切割。

长度（i）|1|2|3|4|5|6|7|8|9|10 -|- 价格（R）|1|5|8|9|10|17|17|20|24|30

给定一个长度为 n 的钢条，该钢条经过有效切割，最多能卖出多少钱？

public class Solution {

  public static int[] prices = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

  private static int maxValue(int n) {
    int[] dp = new int[n + 1];
    for (int j = 1; j <= n; j++) {
      for (int i = 1; i <= j; i++) {
        dp[j] = Math.max(dp[j], prices[i - 1] + dp[j - i]);
      }
    }
    return dp[n];
  }

  public static void main(String[] args) {

    for (int i = 1; i <= prices.length; i++)
      System.out.println("长度为" + i + "的最大收益为：" + maxValue(i));

  }
}

1.找零钱的最少硬币数

322.给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

思路：完全背包问题。

物品：硬币
物品大小：面额
物品价值：数量

class Solution {
 public int coinChange(int[] coins, int amount) {
 if(amount == 0) return 0;
 int[] dp = new int[amount+1];
 for(int coin : coins){
 for(int i = coin; i < amount + 1; i++){
 if(i == coin) dp[i] = 1;
 else if(dp[i] == 0 && dp[i-coin] != 0) dp[i] = dp[i-coin] + 1;
 else if(dp[i] != 0 && dp[i-coin] != 0) dp[i] = Math.min(dp[i], dp[i-coin]+1);
 }
 }
 return dp[amount] == 0 ? -1 : dp[amount];
 }
 }

2.找零钱的硬币数组合

518.给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

思路：完全背包问题。使用 dp 记录可达成目标的组合数目。

class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount+1];
    dp[0] = 1;
    for(int coin : coins){
      for(int i = coin; i < amount + 1; i++){
        dp[i] += dp[i-coin];
      }
    }
    return dp[amount];
  }
}

3.单词拆分

139.给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

  输入: s = "leetcode", wordDict = ["leet", "code"]
  输出: true
  解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

思路：dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 "leetcode"：

["lee", "tc", "cod"]

求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
      for (String word : wordDict) {   // 对物品的迭代应该放在最里层
        int len = word.length();
        if (len <= i && word.equals(s.substring(i - len, i))) {
          dp[i] = dp[i] || dp[i - len];
        }
      }
    }
    return dp[n];
  }
}

分享到QQ

分享到微博