目录

动态规划

动态规划思维（基础）

状态表示（最重要）

状态转移方程（最难）

初始化（细节）

填表顺序（细节）

返回值（结果）

1、第 N 个泰波那契数⭐

【题目解析】

【算法原理】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

2、三步问题⭐

【题目解析】

【算法原理】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组】

C++ 算法代码

复杂度分析

3、使用最小花费爬楼梯⭐

【题目解析一】

【算法原理一】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组一】

C++ 算法代码

复杂度分析

【题目解析二】

【算法原理二】

C++ 算法代码

复杂度分析

【空间优化 - 滚动数组二】

C++ 算法代码

复杂度分析

总结

动态规划

动态规划思维（基础）

        动态规划一般会先定义一个dp表，dp表一般为一维数组 / 二位数组。如：一维数组，会先创建一个一维数组（dp表），接下来就是想办法将这个dp填满，而填满之后里面的某一个值就是最终结果。

状态表示（最重要）

#问：是什么？

• 就是dp[i]所代表的含义。

#问：怎么来？

• 题目要求。
• 经验 + 题目要求。
• 分析问题的过程中，发现重复子问题。

状态转移方程（最难）

#问：是什么？

• dp[i] = ?。

初始化（细节）

#问：有什么作用？

• 保证填表的时候不越界。

        dp表是根据状态转移方程进行的，而状态转移方程是通过已有状态推出未知状态。

填表顺序（细节）

#问：有什么作用？

• 为了填写当前状态的时候，所需要的状态已经计算过了。

返回值（结果）

        题目要求 + 状态表示。

1、第 N 个泰波那契数⭐

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

---

​

【题目解析】

         泰波那契序列 Tn 是从 T0 开始的，也就是说Tn的个数是 n+1 需要注意。

【算法原理】

#：状态表示：

        这道题可以「根据题目的要求」直接定义出状态dp[i] 表示：第 i 个泰波那契数的值。

#： 状态转移方程：

         从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进行推导的，因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。 因此我们需要在填表之前，将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] = 0，dp[1] = dp[2] = 1 。

#：填表顺序：

class Solution {
public:int tribonacci(int n) {// 处理边界情况if(n == 0) return 0;if(n <= 2) return 1;// 1、创建dp表vector<int> dp(n + 1,0);// 2、初始化dp[1] = 1, dp[2] = 1;// 3、填表for(int i = 3; i<=n; i++)dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];// 4、返回值    return dp[n];}
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

【空间优化 - 滚动数组】

        通过上述图可以发现。

        dp[i]是只与前三个元素相关，所以我们可以将代码写为如下：

C++ 算法代码

class Solution {
public:int tribonacci(int n) {// 处理边界情况if(n == 0) return 0;if(n <= 2) return 1;// 1、创建 dp 表vector<int> val(3,0);// 2、初始化val[1] = 1, val[2] = 1;int tmp = 0;// 3、填表for(int i = 3; i<=n; i++){tmp = val[0] + val[1] + val[2];val[0] = val[1], val[1] = val[2], val[2] = tmp;}// 4、返回return tmp;}
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

2、三步问题⭐

 面试题 08.01. 三步问题 - 力扣（LeetCode）

---

【题目解析】

         散步问题 dpn 是从 dp1 开始的，也就是说 Tn 的个数是 n + 1 需要注意，将 pd[0] 单独放在一旁有益于代码的书写。

        对应的阶梯是由前三个阶梯而来。

【算法原理】

#：状态表示：

#： 状态转移方程：

#：填表顺序：

class Solution {
public:int waysToStep(int n) {// 处理边界情况if(n == 1 || n == 2) return n;if(n == 3) return 4;// 1、创建 dp 表vector<int> dp(n + 1, 0);// 2、初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;// 3、填表for(int i = 4; i <= n; i++)dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;// 4、返回return dp[n];}
};

class Solution {
public:int waysToStep(int n) {// 1、创建 dp 表vector<int> dp(4, 0);// 2、初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;// 处理边界情况if(n <= 3) return dp[n];// 3、填表uint64_t tmp = 0;for(int i = 4; i <= n; i++){tmp = ((dp[1] + dp[2]) % 1000000007 + dp[3]) % 1000000007;dp[1] = dp[2], dp[2] = dp[3], dp[3] = tmp;}// 4、返回return tmp;}
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

3、使用最小花费爬楼梯⭐

 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

---

​

【题目解析一】

        pd[i]是由前两个台阶的，所处台阶需花费用 + 所处台阶已花费用的min值。 需要注意的是，此处的顶部并不是n，而是n+1。

【算法原理一】

#：状态表示：

        这道题可以根据「经验 + 题目要求」直接定义出状态dp[i] 表示：到达 i 位置时的最小花费。（注意：到达 i 位置的时候，i 位置的钱不需要算上，先到达，后出发花费）

#： 状态转移方程：

         从我们的递推公式可以看出，我们需要先初始化 i = 0、i = 1 位置的值。容易得到 dp[0] = dp[1] = 0 ，因为不需要任何花费，就可以直接站在第 0 层和第 1 层上。

#：填表顺序：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 1、创建dp表vector<int> dp(cost.size() + 1, 0);// 2、初始化dp[0] = 0, dp[1] = 0;// 3、填表for(int i = 2; i <= cost.size(); i++)dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);// 4、返回return dp[cost.size()];}
};

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);// 1、创建dp表vector<int> dp(2, 0);// 2、初始化dp[0] = 0, dp[1] = 0;// 3、填表int tmp = 0;for(int i = 2; i <= cost.size(); i++){tmp = min(cost[i - 1] + dp[1], cost[i - 2] + dp[0]);dp[0] = dp[1], dp[1] = tmp;}// 4、返回return tmp;}
};

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);int n = cost.size();// 1、创建dp表vector<int> dp(n, 0);// 2、初始化dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];// 3、填表for(int i = n - 3; i >= 0; i--)dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];// 4、返回return min(dp[0], dp[1]);}
};

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 处理边界情况if(cost.size() == 2) return min(cost[0], cost[1]);// 1、创建dp表vector<int> dp(2, 0);// 2、初始化dp[1] = cost[cost.size() - 1], dp[0] = cost[cost.size() - 2];// 3、填表int tmp = 0;for(int i = cost.size() - 3; i >= 0; i--){tmp = min(dp[0], dp[1]) + cost[i];dp[1] = dp[0], dp[0] = tmp;}// 4、返回return min(dp[0], dp[1]);}
};