动态规划练习题（2024/7/18）

什么是动态规划？

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划是一种解决多阶段决策过程最优化问题的数学方法。它通常用于解决具有重叠子问题和最优子结构性质的问题，通过将问题分解为更小的子问题并记录每个子问题的解，最终通过组合这些子问题的解来求得原问题的最优解。动态规划算法通常用于优化问题，如最短路径、最长公共子序列、背包问题等，其核心思想是通过空间换时间，避免重复计算，从而提高效率。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划问题五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

1斐波那契数

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

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

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

思路：

1. 定义dp数组：dp[i] 表示斐波那契数列第i个数的值。

2. 设置初始条件：确定了斐波那契数列的起始值 dp[0] = 0 和 dp[1] = 1。

3. 递推公式：使用经典的递推关系式 dp[i] = dp[i - 1] + dp[i - 2] 计算出每个 dp[i] 的值。

4. 遍历顺序：从 dp[2] 到 dp[N]，依次计算每个值，确保每个子问题的解只计算一次。

5. 举例推导dp数组：通过具体的例子（如计算 dp[5]）来展示每一步计算的过程，加深理解。

 

 // 以N=5为例，计算过程如下：
        // dp[0] = 0
        // dp[1] = 1
        // dp[2] = dp[1] + dp[0] = 1 + 0 = 1
        // dp[3] = dp[2] + dp[1] = 1 + 1 = 2
        // dp[4] = dp[3] + dp[2] = 2 + 1 = 3
        // dp[5] = dp[4] + dp[3] = 3 + 2 = 5

代码：

class Solution {
public:
    int fib(int N) {
        // 如果N小于等于1，直接返回N，因为斐波那契数列中F(0)=0，F(1)=1
        if (N <= 1) return N;
        
        // 创建一个大小为N+1的dp数组，用来存储斐波那契数列的值
        vector<int> dp(N + 1);
        
        // 设置初始条件：斐波那契数列的前两个数
        dp[0] = 0;  // F(0) = 0
        dp[1] = 1;  // F(1) = 1
        
        // 使用动态规划递推公式计算从dp[2]到dp[N]的值
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        // 返回斐波那契数列第N个数的值
        return dp[N];
    }
};

2 爬楼梯

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

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

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

思路：

1. 确定dp数组（dp table）以及下标的含义

在解决爬楼梯问题时，我们定义一个dp数组：

• dp[i] 表示爬到第i阶楼梯的方法总数。

2. 确定递推公式

通过分析可得出递推公式：

• 当 i = 1 时，dp[1] = 1：爬到第1阶楼梯只有一种方法。
• 当 i = 2 时，dp[2] = 2：爬到第2阶楼梯有两种方法（一步一步或者一次两步）。
• 对于 i >= 3，爬到第i阶楼梯的方法数可以通过以下递推关系得到：
  [
  dp[i] = dp[i - 1] + dp[i - 2]
  ]
  解释：要到达第i阶楼梯，可以从第i-1阶走一步，或者从第i-2阶走两步，因此 dp[i] 的值等于这两种方式的方法数之和。

3. dp数组如何初始化

根据递推公式，我们需要初始化前两个元素：

• dp[1] = 1：爬到第1阶楼梯的方法数为1。
• dp[2] = 2：爬到第2阶楼梯的方法数为2。

4. 确定遍历顺序

我们从小到大遍历楼梯的阶数，从 i = 3 开始直到 i = n，计算并填充 dp[i] 的值。

5. 举例推导dp数组

以一个具体的例子（如n=5）来推导dp数组的值：

• 初始化：dp[1] = 1，dp[2] = 2。
• 计算 dp[3]：dp[3] = dp[2] + dp[1] = 2 + 1 = 3。
• 计算 dp[4]：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。
• 计算 dp[5]：dp[5] = dp[4] + dp[3] = 5 + 3 = 8。

因此，爬到第5阶楼梯的方法数为8。

代码：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 如果台阶数小于等于1，则直接返回n，因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1); // 创建一个大小为n+1的动态规划数组
        dp[1] = 1; // 初始化动态规划数组的第一个值为1
        dp[2] = 2; // 初始化动态规划数组的第二个值为2
        for (int i = 3; i <= n; i++) { // 从第三个值开始计算
            dp[i] = dp[i - 1] + dp[i - 2]; // 根据题目要求的规则，计算每个台阶的方法数
        }
        return dp[n]; // 返回达到第n个台阶的方法数
    }
};

3使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

思路：

1. 确定dp数组（dp table）以及下标的含义

在本问题中，我们定义一个dp数组：

• dp[i] 表示到达第i个台阶的最小花费。

2. 确定递推公式

根据题意，可以得出递推公式：

• 到达第 i 个台阶的最小花费 dp[i] 可以由以下两种方式得到：

  • 从第 i-1 个台阶花费 cost[i-1] 走一步到达；
  • 或者从第 i-2 个台阶花费 cost[i-2] 走两步到达。

  因此，递推公式为：
  [
  dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
  ]

3. dp数组如何初始化

根据递推公式，需要初始化前两个元素：

• dp[0] = 0：表示起始时在地面上，不花费任何体力。
• dp[1] = 0：表示从地面上直接跳到第一个台阶，同样不花费体力。

4. 确定遍历顺序

从第三个台阶开始遍历，直到最后一个台阶 cost.size()，计算并填充 dp[i] 的值。

5. 举例推导dp数组

以一个具体的例子来推导dp数组的值（假设 cost = [10, 15, 20]）：

• 初始化：dp[0] = 0，dp[1] = 0。
• 计算 dp[2]：dp[2] = min(dp[1] + 15, dp[0] + 10) = min(0 + 10, 0 + 15) = 10。
• 计算 dp[3]：dp[3] = min(dp[2] + 20, dp[1] + 15) = min(10 + 15, 0 + 15) = 15。

代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1); // 创建一个大小为 cost.size()+1 的动态规划数组
        dp[0] = 0; // 默认第一步都是不花费体力的
        dp[1] = 0; // 默认第二步也是不花费体力的
        for (int i = 2; i <= cost.size(); i++) { // 从第三步开始计算
            // 到达第 i 个台阶的最小花费等于到达第 i-1 个台阶和第 i-2 个台阶的最小花费加上当前台阶的花费的较小值
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()]; // 返回到达顶部台阶的最小花费
    }
};