动态规划入门：斐波那契数列模型以及多状态（C++）
温馨提示：这篇文章已超过387天没有更新，请注意相关的内容是否还可用！
斐波那契数列模型以及多状态
- 动态规划简述
- 斐波那契数列模型
- 1.第 N 个泰波那契数（简单）
- 2.三步问题（简单）
- 3.使⽤最⼩花费爬楼梯（简单）
- 4.解码方法（中等）
- 简单多状态
- 1.打家劫舍（中等）
- 2.打家劫舍II（中等）
- 3.粉刷房子（中等）
- 4.删除并获得点数（中等）
- 5.买卖股票的最佳时期含⼿续费（中等）
- 6.买卖股票的最佳时机含冷冻期（中等）
- 7.买卖股票的最佳时机III（困难）
- 8.买卖股票的最佳时机IV（困难）
动态规划简述
动态规划(Dynamic programming，简称 DP)是一种解决多阶段决策问题的算法思想。它将问题分解为多个阶段，并通过保存中间结果来避免重复计算，从而提高效率。
动态规划的解题步骤一般分为以下几步：
- 思考状态表示，创建dp表(重点)
- 分析出状态转移方程(重点)
- 初始化
- 确定填表顺序
- 确定返回值
斐波那契数列模型
1.第 N 个泰波那契数（简单）
链接：第 N 个泰波那契数
- 题目描述
- 做题步骤
- 状态表示
面对动态规划问题，我们一般有两种状态表示：
- 以某一个位置为起点，……
- 以某一个位置为终点，……
我们一般优先考虑第1种表示，但如果第1种无法解决就考虑第2种。
-
状态转移方程
这个题目直接告诉了我们状态转移方程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
-
初始化
泰波那契数的第0、1、2个是特殊的，不满足状态转移方程，因此我们需要初始化这三个位置为0、1、1
-
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序很明显是从左往右
-
返回值
根据状态表示，假设要求的是第n个，返回的应该是dp[n]
- 代码实现
class Solution { public: int tribonacci(int n) { //对于第0、1、2单独处理 if(n == 0) return 0; if(n == 1 || n == 2) return 1; //dp[i]：第i个泰波那契数 vector dp(n + 1); dp[0] = 0; dp[1] = 1; dp[2] = 1; for(int i = 3; i O(1) O(N^2)->O(N) //但这并不是动态规划讲解的要点，所以我只会把两种优化情况的代码给出 // class Solution { // public: // int tribonacci(int n) // { // if(n == 0) // return 0; // if(n == 1 || n == 2) // return 1; // int t1 = 0; // int t2 = 1; // int t3 = 1; // int ret = 0; // for(int i = 3; i2.三步问题（简单）
链接：三步问题
-
题目描述
-
做题步骤
-
状态表示
-
状态转移方程
到达i阶可以转换成先到达i - 3、i - 2、i - 1阶，三者相加得到结果，所以状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
-
初始化
为了保证填表不越界，我们把到达1、2、3阶的方法初始化。
-
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序从左往右。
-
返回值
根据状态表示，假设要求的是n阶，返回的应该是dp[n]
- 代码实现
class Solution { public: int waysToStep(int n) { //1、2、3阶特殊处理 if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; //dp[i]表示到达i阶的方法数 vector dp(n+1); //多开一个空间，可以让下标和层数对应 dp[1] = 1; dp[2] = 2; dp[3] = 4; const int mod = 1e9 + 7; //有可能超出，需要取模 for(int i = 4; i3.使⽤最⼩花费爬楼梯（简单）
链接：使⽤最⼩花费爬楼梯
-
题目描述
-
做题步骤
-
状态表示
这个题目的思路和第2题很相似，要到达终点n阶，我们可以从n - 1阶走一步、n - 2阶走两步到终点，从中选择费用最低的一方(从当前阶离开需要支付离开费用)；至于到达n - 1、n - 2阶的最低费用，我们可以以n - 1、n - 2层为终点进行分析，依此类推。到达终点的过程需要到达每一层的最低费用，我们可以用一个dp表存储，dp[i]表示到达下标i台阶所需要的最低费用。
-
状态转移方程
到达i阶的最低花费可以转换为min(到达i - 1阶的最低花费 + 走出这一阶的花费， 到达i - 2阶的最低花费 + 走出这一阶的花费)，所以状态转移方程为：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。
-
初始化
由转移方程可知更新某个状态需要前置的两个状态，为了确保填表时不越界，单独处理走到0、1阶的最低花费。
-
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序从左往右。
-
返回值
根据状态表示，假设数组有n个元素(终点是n阶)，返回的应该是dp[n]
- 代码实现
class Solution { public: int minCostClimbingStairs(vector& cost) { //dp[i] 表示到这一层的最小花费 int n = cost.size(); vector dp(n + 1); //一开始就可以在0或1阶，花费为0，vector默认给0，不用处理 for(int i = 2; i = 0; i--) // { // dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]); // } // return min(dp[0], dp[1]); // } // };4.解码方法（中等）
链接：解码方法
-
题目描述
-
做题步骤
-
状态表示
-
状态表示
除去第一位，每个位置都有单独解码和联合解码两种方式，n位置的状态转移方程为：dp[n] = dp[n - 1]（单独解码成功）+ dp[n - 2]（联合解码成功）
-
初始化
依据状态转移方程，某位置状态需要前置的两个状态，为了避免越界，我们需要单独处理第1、2个位置，但观察上面的分析过程，可以发现第2个位置和其它位置一样也有两种解码可能，我们可以在dp表前面多加个虚拟节点并初始为1，这样就只需要处理第1个位置了。（看图看图）
-
填表顺序
保证填当前状态时，所需状态已经计算过，填表顺序从左往右。
-
返回值
依据状态定义，假设序列长度为n，返回的应该是以n位置为结尾的解码可能数，即dp[n]。
- 代码实现
class Solution { public: int numDecodings(string s) { int n = s.size(); //dp[i]表示以i位置为结尾的解码可能数 vector dp(n + 1); //第一个位置就为0，最终结果已经是0 if(s[0] == '0') return 0; //初始化虚拟节点和第1个位置 dp[1] = dp[0] = 1; for(int i = 2; i = 10 && com public: int rob(vector int n = nums.size(); vector f[i] = g[i - 1] + nums[i]; g[i] = max(g[i - 1], f[i - 1]); } return max(f[n - 1], g[n - 1]); //空间复杂度：O(N) //时间复杂度：O(N) } }; public: int _rob(vector //区间不存在返回0 if(left right) return 0; int n = nums.size(); vector f(n); //到这个屋子偷的最大金额 auto g = f; //到这个屋子不偷的最大金额 f[left] = nums[left]; for(int i = left + 1; i f[i] = g[i - 1] + nums[i]; g[i] = max(f[i - 1],g[i - 1]); } return max(f[right],g[right]); } int rob(vector int n = nums.size(); return max(nums[0] + _rob(nums, 2, n - 2), _rob(nums, 1, n - 1)); } }; public: int minCost(vector int n = costs.size(); //dp[i][j]表示第i号房子粉刷成j颜色的最低花费 //其中0表示红色，1表示蓝色，2表示绿色 vector dp[i][0] = costs[i - 1][0] + min(dp[i - 1][1], dp[i - 1][2]); dp[i][1] = costs[i - 1][1] + min(dp[i - 1][0], dp[i - 1][2]); dp[i][2] = costs[i - 1][2] + min(dp[i - 1][0], dp[i - 1][1]); } return min({dp[n][0], dp[n][1], dp[n][2]}); //时间复杂度：O(N) //空间复杂度：O(N) } }; public: int deleteAndEarn(vector int n = nums.size(); //创建数组进行映射 //题目中1 0}; for(auto val : nums) v[val] += val; //“打家劫舍” vector f[i] = g[i - 1] + v[i]; g[i] = max(f[i - 1], g[i - 1]); } return max(f[N - 1],g[N - 1]); //时间复杂度：O(N) //空间复杂度：O(1) } }; //上面的写法简洁一些，但无论数据量多少都会遍历10000次 //可以记录数组的最大、最小值，来加快速度 // class Solution { // public: // int deleteAndEarn(vector // int n = nums.size(); // vector // v[nums[i]] += nums[i]; // _max = max(_max, nums[i]); // _min = min(_min, nums[i]); // } // vector // f[i] = g[i - 1] + v[i]; // g[i] = max(f[i - 1], g[i - 1]); // } // return max(f[_max],g[_max]); // } // }; public: int maxProfit(vector int n = prices.size(); //dp[i][j]:第i天结束处于j状态的最大利润 vector dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee); } return max(dp[n - 1][1], dp[n - 1][0]); //时间复杂度：O(N) //空间复杂度：O(N) } }; public: int maxProfit(vector int n = prices.size(); //dp[i][j]：第i天结束后处于j状态时的最大利润 vector dp[i][0] = max(dp[i - 1][1] - prices[i], dp[i - 1][0]); dp[i][1] = max(dp[i - 1][2], dp[i - 1][1]); dp[i][2] = dp[i - 1][0] + prices[i]; } return max(dp[n - 1][2],dp[n - 1][1]); } }; public: //可能会越界,取INT_MIN的一半 const int INF = INT_MIN / 2; int maxProfit(vector int n = prices.size(); //dp[i][j]表示在第i天结束后完成j次交易，处于""状态下的最大利润 vector for(int j = 0; j
-
-
-
-
-
-
- 做题步骤
