LeetCode刷题—动态规划（一）

发表于 2020-12-29 更新于 2021-01-08 分类于 LeetCode刷题

跟着 labuladong 和 CS-Notes 对动态规划做题、总结，形成自己的模板。 ## 引入动态规划动态规划问题的一般形式就是求最值。求解动态规划的核心问题是穷举。

首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。

解题步骤：

定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序（一般采用自底向上）
空间优化（可选） ## 第一类题型：斐波那契数列。 509，斐波那契数列，easy

母牛生产通过「斐波那契数列问题」明白什么是重叠子问题（斐波那契数列没有求最值，所以严格来说不是动态规划问题）。 #### 509，斐波那契数列，easy

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

方法一：暴力递归。

此解法最好理解，但效率不高，这是因为效率低，由下面的递归树不难发现存在大量重复计算，这就是动态规划问题的第一个性质：重叠子问题。
- 代码：
class Solution {
public int fib(int n) {
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
}
下面，我们想办法解决这个问题。

方法二：带备忘录的自顶向下

先计算存储子问题的答案，然后利用子问题的答案计算当前斐波那契数的答案。我们将递归计算，但是通过记忆化不重复计算已计算的值。

可以用数组或 HashMap 存储已计算过的值。

代码：

class Solution {
	public int fib(int n) {
        int[] memo = new int[n + 1];
        for(int i = 0; i < n + 1; i++){
            memo[i] = 0;
        }
        return helper(memo, n);
    }
    public int helper(int[] memo, int n){
        if(n < 2) return n;
       
        //已经计算过则直接取出
        if(memo[n] != 0) return memo[n];
		//没有计算过
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}

再次画出递归树。

通过剪枝，极大减少了子问题（即递归图中节点）的个数。在这里插入图片描述

方法三：迭代（自底向上）

可以把这个「备忘录」独立出来成为一张表，发现计算index = n 的值只与前两个有关，则自底建立前两个元素。

代码：

class Solution {	
	public int fib(int n) {
       	int first = 0;
       	int second = 1;
       	int sum = 0;
       	while(n-- > 0){
           	sum = first + second;
           	first = second;
           	second = sum;
       }
       return first;
   	}
   }

另一种：

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

#### 70，爬楼梯，easy

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

示例 1：

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

示例 2：

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

思路：
- 我们用 f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
  
  f(x) = f(x - 1) + f(x - 2)
  
  它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。
- 与斐波那契数列的递推式相同，区别在于 f(0) = 1。
- 爬楼梯的过程自底向上。

代码：

class Solution {
//f(n) = f(n - 1) + f(n - 2)
//1 1 2 3 5 8 ...
 	public int climbStairs(int n) {
     	if(n < 2) return 1;
     	int first = 1;
     	int second = 1;
    	 	int sum = 0;
     	for(int i = 1; i < n; i++){
         	sum = first + second;
         	first = second;
         	second = sum;
    	 	}
     return sum;
 	}
 }

另一种：

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

上面两道题可以很好的理解动态规划的重叠子问题，递推关系也很简单，下面通过具体例子理解解题步骤：

定义子问题
写出子问题的递推关系
确定 DP 数组的计算顺序
空间优化（可选） #### 198，打家劫舍，easy

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

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

解题步骤：
1. 定义子问题
  
  原问题是【全部房子偷到的最大金额】，子问题是【小偷到第 k 间房屋时偷到的最大金额】
  
  理解：
  
  子问题是参数化的，我们定义的子问题中有参数 k。假设一共有 n 个房子的话，就一共有 n 个子问题。动态规划实际上就是通过求这一堆子问题的解，来求出原问题的解。这要求子问题需要具备两个性质：
  - 原问题要能由子问题表示。例如这道小偷问题中，k=n 时实际上就是原问题。否则，解了半天子问题还是解不出原问题，那子问题岂不是白解了。
  - 一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中，f(k) 可以由 f(k−1) 和 f(k−2) 求出，具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。
2. 子问题递推关系
  - base case
    
    首先考虑最简单的情况。
    
    1). 只有一间房屋，则偷窃的最高金额为此房屋的金额
    
    2). 只有两间房屋，不能挨着偷，选择金额较高的房屋偷。
    
    用 $dp[k]$ 表示前 k 间房屋能偷窃到的最高总金额
    
    $dp[0] = nums[0]$
    
    $dp[1] = max(nums[0],nums[1])$
  - 状态转移方程
    
    房屋数量大于两间，对第 k (k > 2) 间房屋，有两个选择
    
    1). 偷第 k 间，那么就不能偷第 k - 1 间，偷窃总金额为前 k - 2 间房屋的最高金额与第 k 间房屋金额之和。
  在这里插入图片描述

2). 不偷第 k 间，偷窃总金额为前 k - 1 间房屋的最高金额。

在两个选项中选择最大的一项即为答案。

那么就有如下的状态转移方程：

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

3. 确定 DP 数组的计算顺序

动态规划有两种计算顺序，一种是自顶向下的、使用备忘录的递归方法，一种是自底向上的、使用 dp 数组的循环方法。不过在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的 dp 数组。

此题中 $dp[k]$ 依赖 $dp[k-1]$ 和 $dp[k-2]$，采用自底向上。

代码：

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

       	int[] dp = new int[n]; 
       	//base case
       	dp[0] = nums[0];
       	dp[1] = Math.max(nums[0], nums[1]);

       	for(int i = 2; i < n; i++){
          		dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]); 
       	}
       return dp[n - 1];
   	}
   }

213，打家劫舍Ⅱ，medium

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

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

示例 1：

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

思路：
- 与上一题的区别在于所有房屋相连，即第一间房屋和最后一间房屋不能同时偷窃。
  
  可简化为两个单排列问题：
  1. 不偷第一间房屋，偷窃金额的最大值由从第二间房（nums[1]）到最后一间房（nums[n - 1]）的数组来确定。
  2. 不偷最后一间房屋，偷窃金额的最大值由从第一间房（nums[0]）到倒数第二间房（nums[n - 2]）的数组来确定。
    
    再由上面两种情况得到的结果取最大值。
- 由上题思路，只需在主函数构造两个新的数组进行动态规划，再取最大值即为最后结果。
- 主函数的边界条件：
  
  nums.length = 0 返回 0
  
  nums.length = 1 返回 nums[0]

代码：

class Solution {
   	int n;
   	public int rob(int[] nums) {
       	n = nums.length;
       	if(n <= 0) return 0;
       	if(n == 1) return nums[0];
       
       	//不偷 第一间
       	int[] nums1 = new int[n - 1];
       	//不偷 最后一间
       	int[] nums2 = new int[n - 1];
       	for(int i = 0; i < n - 1; i++){
           	nums1[i] = nums[i + 1];
           	nums2[i] = nums[i];
       	}
       return Math.max(rob_init(nums1), rob_init(nums2));
   	}
       public int rob_init(int[] nums) {
       	n = nums.length;
       	if(n == 0) return 0;
       	if(n == 1) return nums[0];

       	int[] dp = new int[n]; 
       	//base case
      	 	dp[0] = nums[0];
       	dp[1] = Math.max(nums[0], nums[1]);

       	for(int i = 2; i < n; i++){
          		dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]); 
       	}
       return dp[n - 1];
   	}
   }

#### 信件错排问题

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

示例1：

输入：N = 2
输出：1

示例2：

输入：N = 3
输出：2

示例3：

输入：N = 4
输出：9

思路：
1. 定义子问题
  
  原问题是【N 个信和信封的错装方式数量】，子问题是【第 i 个信和信封的错装方式数量】
2. 子问题递推关系
  - base case
    
    首先考虑最简单的情况。用 $dp[k]$ 表示前 i 个信和信封的错装方式数量。
    
    1). N = 0，数量为 0 => $dp[0] = 0$
    
    2). N = 1，数量为 0 => $dp[1] = 0$
    
    3). N = 2，数量为 1 => $dp[2] = 1$
  - 状态转移方程
    
    i > 2 时，信封错装方式有两种可能。
    
    1). 对信件 i 和信件 j，如果信件 i 装入信封 j，信件 j 装入信封 i，i 、j 互换后正确。其余 i - 2 个信件装错的数量为 $dp[i - 2]$，j 的选择有$ (i - 1)$ 种。此情况的错装方式数量为 $(i - 1) * dp[i - 2]$
    
    2). 对信件 i 和信件 j，如果信件 i 装入信封 j，信件 j 装入信封 k，i 、j 互换后只有 j 正确。其余 i - 1 个信件装错的数量为 $dp[i - 1]$，j 的选择有$ (i - 1)$ 种。此情况的错装方式数量为 $(i - 1) * dp[i - 1]$
    
    那么就有如下的状态转移方程：
    
    $dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])$

代码：

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

#### 母牛生产

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

示例：

输入：N = 1
输出：1

输入：N = 2
输出：2

输入：N = 3
输出：3

输入：N = 4
输出：4

思路：
1. 定义子问题
  
  原问题为【N 年后牛的数量】，子问题是【第 i 年的牛数量】
2. 子问题递推关系
  - base case
    
    i <= 4 时，只有第一头母牛和它生的小母牛。设 $dp[i]$ 为第 i 年的牛数量。
    
    $dp[0] = 0$、$dp[1] = 1$、$dp[2] = 2$、$dp[3] = 3$
  - 状态转移方程
    
    i > 4 时，第一头母牛生产的小母牛也开始生产。此时牛的数量为上一年牛的数量 $dp[i - 1]$ 加上三年前牛的数量（即第 i 年有生产能力的牛的数量）$dp[i - 3]$，即
    
    $dp[i] = dp[i - 1] + dp[i - 3]$

代码：

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

------ 本文结束感谢您的阅读 ------