动态规划入门:以斐波那-契数列为例_有一个数列定义如下: a 0 = 1 , a 1 = 1 , a n = ( a n 1 + a
1.第 N 个泰波那契数
题目链接
泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n
,请返回第 n 个泰波那契数 Tn 的值。
示例 1:
输入: n = 4
输出: 4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2:
输入: n = 25
输出: 1389537
dp[i]就是第i个泰波那契数
我们这个题直接返回dp[n]就行了
为了保证不出现越界的情况,我们将前3个位置进行初始化,这里题目中已经说了具体初始化为什么
填表的顺序是从左向右进行就行了
class Solution{public: int tribonacci(int n) { //处理边界问题(n太小的话是会出现越界的情况的) if(n==0)return 0; if(n==1||n==2)return 1; //1.创建一个dp表 vectordp(n+1); //2.初始化 dp[0]=0,dp[1]=dp[2]=1; //3.填表 for(int i=3;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } //4.返回值 return dp[n]; }};
可以利用滚动数组进行空间优化
就是创建四个变量然后一直不停的移动
class Solution{public: int tribonacci(int n) { //处理边界问题(n太小的话是会出现越界的情况的) if(n==0)return 0; if(n==1||n==2)return 1; int a=0,b=1,c=1,d=0; //3.填表 for(int i=3;i<=n;i++) { d=a+b+c; //三个指针往右边进行移动操作 a=b; b=c; c=d; } //4.返回值 return d; }};
2.三步问题
题目链接
三步问题。有个小孩正在上楼梯,楼梯有 n 阶台阶,小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模 1000000007。
示例 1:
输入:n = 3
输出:4
说明: 有四种走法
示例 2:
输入:n = 5
输出:13
提示:
- n 范围在[1, 1000000]之间
这里我们的dp[i]分成三种情况
从[i-1]位置走一步到[i]位置 dp[i-1]种方法
从[i-2]位置走两步到[i]位置 dp[i-2]种方法
从[i-3]位置走三步到[i]位置 dp[i-3]种方法
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
初始化:保证不越界
先将前三个进行初始化操作
dp[1]=1
dp[2]=2
dp[3]=4
class Solution{public: int waysToStep(int n) { const int MOD=1e9+7; //创建一个dp表 vectordp(n+1); //边界条件处理 if(n==1||n==2)return n; if(n==3)return 4; //填表之前进行一个初始化操作 dp[1]=1,dp[2]=2,dp[3]=4; //开始填表 for(int i=4;i<=n;i++) dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;//每次做加法的时候取模,防止越界操作了 //确定返回值 return dp[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 。
dp[i]标示的是到达i位置的最小花费
初始化
保证填表的时候不越界
我们是需要将dp表前两个位置进行初始化操作
dp[0]和dp[1]都初始化为0
结果返回dp[n]就行了
class Solution{public: int minCostClimbingStairs(vector& cost) { //创建一个dp表 //2.初始化 //3.填表 //4.返回结果 int n=cost.size(); vectordp(n+1); //dp[0]=dp[1]=0; 我们这里就不需要写了,因为我们在创建dp表的时候已经进行了初始化操作了 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]; }};
解法二:从i位置为起点
dp[i]标示:从i位置出发,到达楼顶,此时的最小花费
class Solution{public: int minCostClimbingStairs(vector& cost) { //创建一个dp表 //2.初始化 //3.填表 //4.返回结果 int n=cost.size(); vectordp(n); dp[n-1]=cost[n-1]; dp[n-2]=cost[n-2]; for(int i=n-3;i>=0;i--) { dp[i]=cost[i]+min(dp[i+1],dp[i+2]); } return min(dp[0],dp[1]); }};
4.解码方法
解码方法
一条包含字母 A-Z
的消息通过以下映射进行了 编码 :
\"1\" -> \'A\' \"2\" -> \'B\' ... \"25\" -> \'Y\' \"26\" -> \'Z\'
然而,在 解码 已编码的消息时,你意识到有许多不同的方式来解码,因为有些编码被包含在其它编码当中(\"2\"
和 \"5\"
与 \"25\"
)。
例如,\"11106\"
可以映射为:
\"AAJF\"
,将消息分组为(1, 1, 10, 6)
\"KJF\"
,将消息分组为(11, 10, 6)
- 消息不能分组为
(1, 11, 06)
,因为\"06\"
不是一个合法编码(只有 “6” 是合法的)。
注意,可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串 s
,请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串,返回 0
。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
输入: s = “12”
输出: 2
**解释:**它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2:
输入: s = “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3:
输入: s = “06”
输出: 0
解释:“06” 无法映射到 “F” ,因为存在前导零(“6” 和 “06” 并不等价)。
提示:
1 <= s.length <= 100
s
只包含数字,并且可能包含前导零。
dp[i]表示:以i位置为结尾时,解码方法的总数
所以我们的状态方程就是dp[i]=dp[i-1]+dp[i-2]
返回值是dp[n-1]
class Solution{public: int numDecodings(string s) { //创建dp表 //初始化 //填表 //返回值 int n=s.size(); vectordp(n+1); //初始化一开始的两个位置的dp表 dp[0]=s[0]!=\'0\';//说明能单独编码 //处理下边界条件 if(n==1)return dp[0];//如果只有一个字符的话我们直接返回dp[0]就行了 if(s[0]!=\'0\'&&s[1]!=\'0\')dp[1]+=1;//第一个位置和第二个位置都能单独编码 int t=(s[0]-\'0\')*10+s[1]-\'0\';//前两个位置所表示的数 if(t>=10&&t<=26)dp[1]+=1; //上面已经将前两个位置初始化好了,现在我们从第三个位置进行初始化操作就行了 for(int i=2;i=10&&t<=26)dp[i]+=dp[i-2]; } return dp[n-1]; }};
这里初始化的长度太长了,我们可以进行优化下
其实就是处理边界问题和初始化问题的技巧
注意事项:
1.虚拟节点里面的值,要保证后面的填表是正确的
2.下标的映射关系
就是将我们的dp表往右边挪动了一位
class Solution{public: int numDecodings(string s) { //创建dp表 //初始化 //填表 //返回值 int n=s.size(); vectordp(n+1); //初始化一开始的两个位置的dp表 dp[0]=1;//虚拟节点初始化为1,保证后面的填表是正确的 dp[1]=s[1-1]!=\'0\'; //上面已经将前两个位置初始化好了,现在我们从第三个位置进行初始化操作就行了 for(int i=2;i=10&&t<=26)dp[i]+=dp[i-2]; } return dp[n]; }};
这里所有要设计到找之前的字符的,我们都要多减一个1