【动态规划】风雨不动安如山，赖有砥柱立中流 - 斐波那契数列模型
【动态规划】风雨不动安如山，赖有砥柱立中流 - 斐波那契数列模型
1. 第 N 个泰波那契数
题目链接: 1137. 第 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
第一 步骤分析
1. 状态表示
dp[i] 表示: 第 i 个泰波契数的值
2. 状态转移方程
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2. 由题意可知状态方程: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 一般来说状态方程都是需要自己分析出来的, 此题比较简单, 直接给出.
3. 初始化
保证状态转移方程中的dp值不越界, 即填写dp 表不越界. 由题可知: dp[0] = 0,dp[1] = 1,dp[2] = 1;
4. 填表顺序
从左到右填表, 因为要想直到dp[i], 必须先知道dp[i-1],dp[i-2],dp[i-3].
5. 返回值
由题可知返回第 n 个泰波那契数 Tn 的值。return dp[n]即可
第二 代码实现
class Solution {
public int tribonacci(int n) {
//1.创建一个dp表
int[] dp = new int[n+1];
//2.初始化
if(n == 0) return n;
if(n == 1 || n == 2) return 1;
dp[0] = 0;dp[1] = 1;dp[2] = 1;
//3.填表
for(int i = 3;i <= n;++i) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
return dp[n];
}
}2. 三步问题
题目链接: 面试题 08.01. 三步问题
题目内容:
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3 输出：4 说明: 有四种走法 示例2:
输入：n = 5 输出：13 提示:
n范围在[1, 1000000]之间
第一 步骤分析
1. 状态表示
dp[i] 表示以 i 为结束位置的总的上楼梯方式.
2. 状态转移方程
分析可得, dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
3. 初始化
避免填表时越界, 要对dp表先进行初始化, 从1下标开始, 0下标没有意义, dp[1] = 1, dp[2] = 2, dp[3] = 4.
4. 确定填表顺序
从左到右, 根据状态方程来确定.
5. 返回值
根据题目return dp[n]
第二 代码实现
class Solution {
public int waysToStep(int n) {
//1.创建dp表
int[] dp = new int[n+1];
//2.初始化
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
dp[1] = 1;dp[2] = 2;dp[3] = 4;
int MOD = (int)(1e9 + 7);
//3.填表
for(int i = 4;i <= n;++i) {
dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
}
return dp[n];
}
}3. 使用最小花费爬楼梯
题目链接: 746. 使用最小花费爬楼梯
题目内容:
给你一个整数数组 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 。
第一 步骤分析
1. 状态表示
具体怎么得出状态表示,根据题目要求和做题经验得出. dp[i] 表示: 以 i 位置为结尾的最小花费
2. 状态转移方程
第一种情况从 i-2 位置直接到 i 位置, dp[i] = dp[i-2] + cost[i-2]; 第二种情况从 i-1 位置直接到 i 位置, dp[i] = dp[i-1] + cost[i-1]; 每次求dp[i] 取二者的最小值即可.
3. 初始化
保证状态转移方程中的dp值不越界, 即填写dp 表不越界. 由题可知: dp[0] = 0,dp[1] = 1,dp[2] = 1;
4. 填表顺序
从左到右填表, 因为要想直到dp[i], 必须先知道dp[i-1],dp[i-2],dp[i-3].
5. 返回值
由题可知返回第 n 个泰波那契数 Tn 的值。return dp[n]即可
第二 代码实现
class Solution {
public int minCostClimbingStairs(int[] cost) {
//1.创建dp表
int n = cost.length;
int[] dp = new int[n+1];
//2.初始化
dp[0] = dp[1] = 0;
//3.填表
for(int i = 2;i <= n;++i) {
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
}4. 解码方法
题目链接: 91. 解码方法
题目内容:
一条包含字母 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. 状态表示
dp[i] 表示以 i 位置为结尾的解码方法总数.
2. 状态转移方程
一半都是从 i 的最近位置来找递推关系 第一种情况是 s[i] 单独解码, 当 s[i] != '0’时,解码成功,由上分析图可分析出 此时 dp[i] += dp[i-1]; 当 s[i] == '0’时, dp[i] += 0; 第二种情况是 s[i] 与 s[i-1] 整体解码, 需要先转化为 int 类型,假设二者转化为int 后的值赋给 tmp, 当tmp >= 10 && tmp <= 26时, 同理, dp[i] += dp[i-2];
3. 初始化
保证状态转移方程中的dp值不越界, 即填写dp 表不越界, 需要先将dp[0] 和 dp[1] 先初始化. 先处理0下标位置. 当s[i] != '0’时, dp[0] = 1; 再处理1下标位置. 当s[i] != ‘0’ && s[1] != ‘0’ 时, dp[1] += 1; int t = (s[i-1] - ‘0’) * 10 + s[i] - ‘0’; 当 t >= 10 && t <= 26, dp[1] += 1;
4. 填表顺序
从左到右填表, 因为要想直到dp[i], 必须先知道dp[i-1],dp[i-2]
5. 返回值
由题可知返回 dp[n-1];
第二 代码实现
class Solution {
public int numDecodings(String s) {
//1. 创建dp表
//2. 初始化
//3. 填表
//4. 返回值
//1. 创建dp表
int n = s.length();
char[] ch = s.toCharArray();
int[] dp = new int[n];
//2. 初始化
// 初始化第一个位置
if(ch[0] != '0') {
dp[0] = 1;
}
//处理边界情况
if(n == 1) return dp[0];
// 初始化第二个位置
if(ch[0] != '0' && ch[1] != '0') dp[1] += 1; //注意合并来看,有一个为0都不行.
int t = (ch[0] - '0') * 10 + ch[1] - '0';//找到 dp[0] dp[1] 合并后两者所对应的数.
if(t >= 10 && t <= 26) dp[1] += 1;
//3. 填表
for(int i = 2;i < n;i++) {
if(ch[i] != '0') dp[i] += dp[i-1];
int tmp = (ch[i-1] - '0') * 10 + ch[i] - '0';
if(tmp <= 26 && tmp >= 10 ) dp[i] += dp[i-2];
}
return dp[n-1];
}
}第三 处理初始化和边界请况的技巧 -> 创建出一个虚拟空间
创建新的dp表比字符串 s 的长度多1.
旧dp表的 1 位置初始化其实跟填表时的逻辑是一致的, 所以不如把旧dp[1] 放到填表中填. 看上图, 旧dp[1] 变成了 新dp[2] . 要保证后续填表的正确需要处理好新dp[0].
注意: 1. 新dp与 字符数组ch的下标对应关系是 dp[i] -> s[i-1] 和 s[i-2] 即, 当dp[2] = dp[1] + dp[0], s[1] 和 s[0] 都应满足相应条件 2. 一般来说 dp[0] = 0 , 但此题的 dp[0] = 1, 因为dp[2] = dp[1] + dp[0] , 只要s[0] 和 s[1] 满足条件, 那么dp[2] = 2.
class Solution {
public int numDecodings(String s) {
//1. 创建dp表
//2. 初始化
//3. 填表
//4. 返回值
//1. 创建新dp表
int n = s.length();
char[] ch = s.toCharArray();
int[] dp = new int[n+1];
//2. 初始化
// 初始化第一个位置
dp[0] = 1;
// 初始化第二个位置
if(ch[0] != '0') dp[1] = 1;
//3. 填表
for(int i = 2;i <= n;i++) {
if(ch[i-1] != '0') dp[i] += dp[i-1];
int tmp = (ch[i-2] - '0') * 10 + ch[i-1] - '0';
if(tmp <= 26 && tmp >= 10 ) dp[i] += dp[i-2];
}
return dp[n];
}
}总结: 以后遇到动态规划的题, 能使用初始化的技巧就使用, 不能使用再另外分析.
本篇博客分享到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊
腾讯云开发者
