【动态规划算法】专题一——斐波那契数列模型
一、面试题 08.01. 三步问题
Leetcode链接
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
示例 1：
输入：n = 3
输出：4
说明：有四种走法
n 范围在[1, 1000000]之间
解题思路
- 我们可以发现从地平面（0号）到 i 号台阶的走法数量=0—>i-1号台阶走法数量+0—>i-2号+0—>i-3号，因为这些台阶都可以直接走一次就到达i号台阶，这样我们就可以使用dp算法，而上面就是本题的状态转移方程
再复习一下dp算法解题时的5个关键点：
dp算法就是围绕着dp表来做文章的，那么有以下几点：
- 状态表示
一般就以题目的要求为准，比如题目问什么dp[i]就是什么，还有就是要多写动态规划的题目积累经验 - 状态转移方程
去找当前状态与其相近的一个或几个状态之间的关系，如：本题的相近台阶、矩阵的相邻格子 - 初始化
dp表一般都需要初始化，这是很重要的一步 - 填表顺序
- 返回值（使用dp表）
代码实现及解析
class Solution {
public int waysToStep(int n) {
int MOD=(int)1e9+7;//先定义一下取模数，方便一会书写
int[] dp=new int[n+1];//dp表
//状态表示：dp[i]表示从地平面（0号）到i号台阶的方式总数
if(n==1||n==2) return n;
if(n==3) return 4;//防止dp表越界
dp[1]=1;dp[2]=2;dp[3]=4;//dp表的初始化
//填表：
for(int i=4;i<=n;i++){
dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;//状态转移方程
}
/*
关于这个取模为什么不直接全部相加再%MOD：
风险：在求和时，三个 dp 值可能都非常大。三个这样的数相加，中间结果最大可能接近3,000,000,020
这超过了32位 int 型整数的最大值（2,147,483,647），会导致整数溢出，变成一个负数。虽然对这个
负数取模最终能得到“恰好正确”的结果，但溢出行为本身在Java中是一种未定义的行为，依赖于具体的
JVM实现，严格来说是不安全的。
*/
return dp[n];//使用dp表
}
}
总结
复习解题思路
二、使用最小花费爬楼梯
Leetcode链接
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
提示：
2 <= cost.length <= 1000
从示例一可以看出“楼顶”不包含在cost数组中，不然如果“20”代表楼顶的话，该实例的结果就应该是10，所以cost中存放的都是有效台阶
解题思路
方法一（从固定的起点到变化的终点）：
- 我们可以使dp[i]表示从起点到第i个台阶所需的最少的费用，这样填到第n个台阶（cost值不存在，代表的是楼顶）时就得到了结果
- 状态转移方程：我们发现i-1号台阶、i-2号台阶都可以一步到达i号台阶，所以从起点到第i个台阶所需的最少的费用=min(“从起点先到第i-1个台阶所需的最少的费用+cost[i-1]” ， “从起点先到第i-2个台阶所需的最少的费用+cost[i-2]” )。所以状态转移方程就是：
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
方法二（从变化的起点到固定的终点）：
- 我们可以使dp[i]表示从第i个台阶到楼顶所需的最少的费用，那这个填表顺序肯定是从后往前的，因为我们率先知道后两个台阶到楼顶的最少费用，这样等到将前两个台阶都填完时就得到了结果
- 状态转移方程：我们发现i号台阶可以一步到达i+1号台阶、i+2号台阶，所以从第i个台阶到楼顶所需的最少的费用=min(“从i位置先一步走到i+1位置所需费用+从i+1位置到楼顶所需的最少的费用” ， “从i位置先一步走到i+2位置所需费用+从i+2位置到楼顶所需的最少的费用” )。所以状态转移方程就是：
dp[i]=Math.min(dp[i+1],dp[i+2])+cost[i]
代码实现及解析
//方法一（从固定的起点到变化的终点）：
class Solution1 {
public int minCostClimbingStairs(int[] cost) {
int n=cost.length;
int[] dp=new int[n+1];//dp表的大小要+1，因为要填到n位置（代表楼顶）
//状态表示：从起点到第i个台阶所需的最少的费用
/*
初始化：前两个下标位置需要初始化为0（到第0号、1号台阶的最小费用就是从其本身为起点的情况，费用为0），但储存的值默认就为0
*/
//填表：
for(int i=2;i<n+1;i++){
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);//状态转移方程
}
return dp[n];//使用dp表
}
}
//方法二（从变化的起点到固定的终点）：
class Solution2 {
public int minCostClimbingStairs(int[] cost) {
int n=cost.length;
int[] dp=new int[n];
//状态表示：从第i个台阶到楼顶所需的最少的费用
dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];//初始化：从后两个台阶到楼顶所需的最小费用就是从其本身自己一步到楼顶，所以费用就是cost[i]
//填表：
for(int i=n-3;i>=0;i--){
dp[i]=Math.min(dp[i+1],dp[i+2])+cost[i];//状态转移方程
}
return Math.min(dp[0],dp[1]);//使用dp表
}
}
总结
复习解题思路这两个“反着来”的解题思路非常具有代表性，在上一专题中【不同路径】这个题目中“机器人从起点到终点”问题所使用的核心思想是非常相似的，该题也可以像本题一样使用两种反着来的方法，所以其实该题也完全可以使用dp算法来解决，并且【不同路径】这道题我虽然没有用dp写，但它却是下一专题“路径问题”很重要的一个模板波波老师讲状态表示的确定在dp题目中是重难点，需要大量做题积累经验，而本题这种“以某位置为起点.....”或者“以某位置为终点....”类似这样的思想恰恰就是常见的寻找状态表示的常用方法
三、解码方法
Leetcode链接
一条包含字母 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.length <= 100
s 只包含数字，并且可能包含前导零。
解题思路
- 本题利用了“寻找递归子问题”的方法来找到了解题思路，循着常见的套路，我们看看是否符合“大问题=小部分+剩余大部分—>剩余大部分又=小部分+再次剩余的大部分”，我们发现整个集合的数字之间合法的组合方式总数=先确定第一个被解码数+剩下的大部分数据集合的组合方式总数。
- 而第一个被解码数的确定要分类讨论：我们从后往前遍历进行组合（从前往后也一样）：
- s[i]可以单独作为第一个被解码数
- s[i]和s[i-1]位置可组合成一个合法数，则这个组合数可作为第一个被解码数
- 每次将上面两个方法中合法的情况进行统计就可得出答案
代码实现及解析
class Solution {
public int numDecodings(String _s) {
int n=_s.length();
char[] s=_s.toCharArray();
int[] dp=new int[n];
//状态表示：dp[i]表示从起点到i位置这段范围内的数字的解码方法的总数
if(s[0]!='0') dp[0]=1;//初始化0下标位置
if(n==1) return dp[0];
//初始化1下标位置：
if(s[0]!='0'&&s[1]!='0') dp[1]+=1;
int tmp1=(s[0]-'0')*10+s[1]-'0';
if(tmp1>=10&&tmp1<=26) dp[1]+=1;
//填表：
for(int i=2;i<n;i++){
//状态转移方程（分情况讨论）：
if(s[i]!='0') dp[i]+=dp[i-1];//若i位置单独就合法，s[i]可单独作为第一个被解码数
int tmp2=(s[i-1]-'0')*10+s[i]-'0';
if(tmp2>=10&&tmp2<=26) dp[i]+=dp[i-2];//若i位置和i-1位置可组合成一个合法数，则这个组合数可作为第一个被解码数
}
return dp[n-1];
}
}
- 我们可以发现上面代码中对下标1位置的初始化比较麻烦，对于dp问题，我们会经常遇到边界情况—>对dp表进行初始化解决边界情况，而面对初始化比较麻烦而导致代码变得繁琐的情况有一个常用的技巧：将dp表扩大一格（这样可以将有效数据往后挪一格），二维矩阵的话就扩大一行＋一列，或者是看情况扩展
- 将dp表扩大之后原来的边界情况就会被削减甚至是消除，代码就变得简洁了，当然这样一来就要注意好信息填写时变化后的下标的一一映射关系以及由于dp表的扩容而产生的其他潜在问题（比如多出来的0下标位置是不是仍需事先存放有效信息？本题就是这样）
对dp表进行扩大的优化：
//dp表扩容优化后版本：
class Solution {
public int numDecodings(String _s) {
int n=_s.length();
char[] s=_s.toCharArray();
int[] dp=new int[n+1];
//状态表示：dp[i]表示从起点到i-1位置这段范围内的数字的解码方法的总数（注意这里扩容之后的变化）
if(s[0]!='0') dp[1]=1;
dp[0]=1;//【重点】
//填表：
for(int i=2;i<=n;i++){
//状态转移方程（分情况讨论）：
if(s[i-1]!='0') dp[i]+=dp[i-1];//若i-1位置单独就合法，s[i-1]可单独作为第一个被解码数
int tmp2=(s[i-2]-'0')*10+s[i-1]-'0';
if(tmp2>=10&&tmp2<=26) dp[i]+=dp[i-2];//若i-1位置和i-2位置可组合成一个合法数，则这个组合数可作为第一个被解码数
}
return dp[n];
}
}
为什么代码中dp[0]位置虽然不表示任何有效数据，还要要初始化为1？
- 首先这肯定不是套路，而是分析代码而来的
- 扩容之后状态转移方程没变，仅仅是对应下标更改一下，所以dp表中其他位置的计算不受影响，但是要注意扩容之后原dp[1]不再需要手动初始化，而是放到了for循环里以dp[2]的形式利用状态转移方程进行计算，这正是优化之处。但是由于它是新加入的，你要亲自推演一遍其在for循环中是否可以正确计算（一般无论一维、二维，扩容之后的问题都是这个）
- 结果发现在
dp[i]+=dp[i-2]这一步中i=2，dp[i-2]为dp[0]，所以dp[2]（表示到s中1下标位置的范围…）无法正确更新结果，所以为了这个特殊情况，需要“故意”在dp[0]中存储个1
总结
复习解题思路和代码注释
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)