算法沉淀 —— 动态规划篇(斐波那契数列模型)
前言
几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此
- 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。
以i为结尾
,dp[i] 表示什么,通常为代求问题(具体依题目而定)以i为开始
,dp[i]表示什么,通常为代求问题(具体依题目而定)
- 动态规划问题中,如果直接使用状态转移方程通常会伴随着
越界访问
等风险,所以一般需要初始化。而初始化最重要的两个注意事项便是:保证后续结果正确,不受初始值影响;下标的映射关系
。 - 而
初始化一般分为以下两种:
直接初始化开头的几个值。
一维空间大小+1,下标从1开始;二维增加一行/一列
。
- 4、填dp表、填表顺序:根据状态转移方程来确定填表顺序。
- 5、确定返回值
一、第 N 个泰波那契数
【题目链接】:1137. 第 N 个泰波那契数
【题目】:
【分析】:
题目要第n个斐波那契数,我们令dp[i]表示第i个斐波那契数。题目中以及给出了状态转移方程:dp[i] = dp[i-1] + dp[i-2] +dp[i-3]
。但我们发现当i为0、1、2时显然状态转移方程错误,还会越界访问。所以我们仅需将前3个元素特殊处理,然后在从下标2开始填dp表。最后返回结果即可!
【代码实现】:
class Solution { public: int tribonacci(int n) { if(n == 0) return 0; else if(n == 1 || n == 2) return 1; //创建dp表 vector<int> dp(n + 1); //初始化 dp[0] = 0, dp[1] = dp[2] = 1; //填表 for(int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; return dp[n]; } };
二、三步问题
【题目链接】:面试题 08.01. 三步问题
【题目】:
三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。
【分析】:
我们可以定义dp[i]表示小孩走到i阶台阶时上楼方式的最大值。由题目可知,小孩一次可以走1阶、2阶、3阶。所以我们容易得到状态转移方程为dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
(题目明确表示结果肯过大,记得模1000000007!!)。
显然你以及观察到当i <=3时,状态转移方程不适应。所以我们可以提前将前3个dp表中的值进行初始化;然后在从左往右依次填表。最后返回结果即可!!
【代码实现】:
class Solution { public: int waysToStep(int n) { //特殊处理 if(n == 1) return 1; else if(n == 2) return 2; else if(n == 3) return 4; const int DEL = 1000000007; vector<int> dp(n + 1);//创建dp表,多开一个空间,让下标对应 //初始化 dp[1] = 1, dp[2] = 2, dp[3] = 4; //填表 for(int i = 4; i <= n; i++) dp[i] = (dp[i - 1] + (dp[i - 2] + dp[i - 3]) % DEL) % DEL; return dp[n]; } };
三、使用最小花费爬楼梯
【题目链接】:746. 使用最小花费爬楼梯
【题目】:
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
实例:
【分析】
我们可以用dp[i]变化到达下标为i的台阶时的最低花费。题目中指出,一步可选择向上爬一个或者两个台阶。所以dp[i]必然是从i-1阶或i-2阶台阶爬上来的,易得状态转移方程为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
。
显然当i为0、1时需要单独处理(处理为0)。但C++vector创建dp表时,已经将所有数据初始化为0,所以此步不需要单独实现。然后就是从下标2开始,从左往右依次填dp表了。最后返回结果即可!!
【代码实现】:
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { //创建dp表 int n = cost.size(); vector<int> dp(n + 1); //填表 for(int i = 2; i <= n; i++) dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); return dp[n]; } };
四、解码方法
【题目链接】:91. 解码方法
【题目】:
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
'A' -> "1" 'B' -> "2" ... 'Z' -> "26"
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:
“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的非空字符串 s ,请计算并返回解码方法的总数 。题目数据保证答案肯定是一个32位的整数。
【分析】:
我们定义dp[i]表示从下标[0, i]的子字符串的解法方式总数。显然解码到dp[i]的最近一步分为:从[0,i-1] 加s[i],如果s[i]合法,此时d[i] += dp[i-1];从[0, i-2] 加s[i-1,i],如果s[i-1, i]合法,此时dp[i] += dp[i-2]。所以我们可以得到对应的状态转移方程。(具体看代码)
显然我们需要将dp[1]、dp[2]单独处理,就不多说了。然后从左往右依次填表,最后返回结果!!
【代码实现】:
class Solution { public: int numDecodings(string s) { int n = s.size(); //创建dp表 vector<int> dp(n); //初始化 dp[0] = s[0] != '0'; if(n == 1) return dp[0]; if(s[0] != '0' && s[1] != '0') dp[1]++; int tmp = (s[0] - '0') * 10 + s[1] - '0'; if(tmp >= 10 && tmp <= 26) dp[1]++; //填表 for(int i = 2; i < n; i++) { if(s[i] != '0') dp[i] += dp[i - 1]; int tmp = (s[i - 1] - '0') * 10 + s[i] - '0'; if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2] ; } return dp[n - 1]; } };