【动态规划】斐波那契模型 dp
动态规划的步骤：
- 状态表示。所谓状态表示就是 dp 表里的值表示什么含义，那么状态表示怎么找呢？ a. 题目要求 b. 经验（以某一个位置为结尾 / 起点） + 题目要求 c. 分析问题的过程中发现重复子问题
- 状态转移方程。dp[ i ] 等于什么
- 初始化。保证填表的时候不越界
- 填表顺序。保证填写当前状态时，所需要的状态已经计算过了，初始化之后，下标的映射关系要一致
- 返回值。根据题目要求和状态表示进行返回
1. 第 N 个泰波那契数
这题比较简单，直接秒了
状态表示：dp[i] 表示第 i 个泰波那契数的值
状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
初始化：把前三个数初始化
填表顺序：从左到右
返回值：返回 dp[n]
class Solution {
public int tribonacci(int n) {
int[] dp = new int[38];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
if(n < 3){
return dp[n];
}
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}还可以对上述代码进行空间优化，因为在求第 i 个位置的时候，只需要知道前三个数即可，每次求一个位置都是这样，所以就可以定义三个变量，不断地更新，实现滚动数组的效果
滚动数组空间优化版本：
class Solution {
public int tribonacci(int n) {
int sum = 0;
int a = 0,b = 1,c = 1;
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
for (int i = 3; i <= n; i++) {
sum = a + b + c;
a = b;
b = c;
c = sum;
}
return sum;
}
}2. 面试题 08.01. 三步问题
状态表示：dp[i] 表示到达第 i 个位置时的方案数
状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
初始化：计算前三个数的方案数，把前三个数初始化
填表顺序：从左到右
返回值：返回 dp[n]
class Solution {
public int waysToStep(int n) {
long a = 1,b = 2,c = 4;
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
long res = 0;
for(int i = 4;i <= n;i++){
res = (a + b + c) % 1000000007;
a = b;
b = c;
c = res;
}
return (int) res;
}
}3. 使用最小花费爬楼梯
状态表示：dp[i] 表示到达第 i 个位置时的最小花费
状态转移方程：
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
初始化：由于需要用到前两个数，所以需要把 dp[0] 和 dp[1] 初始化，因为刚开始可以直接从 0 下标或 1 下标出发，所以可以初始化为 0
填表顺序：从左到右
返回值：返回 dp[n]，楼梯顶部为 n 下标，也就是
Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2])
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
if (n == 1 ) return 0;
if(n == 2) return Math.min(cost[0],cost[1]);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i < n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]);
}
}还有第二种状态表示可以解决：
dp[i] 表示从 i 位置出发，到达楼顶的最小花费
初始化：用这种方法的话，就需要用到后面两个元素，所以刚开始初始化需要把最后的两个元素初始化
初始 dp[n - 1] 时就表示从 n - 1 位置支付 cost[n - 1] 就可以直接到达楼顶，dp[n - 2] 时支付 cost[n - 2] 也可以直接到达楼顶
填表顺序：从后往前
最后的返回值也就是 dp[0] 和 dp[1] 的最小值
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
if (n == 1 ) return 0;
if(n == 2) return Math.min(cost[0],cost[1]);
dp[n - 1] = cost[n - 1];
dp[n - 2] = cost[n - 2];
for(int i = n - 3;i >= 0;i--){
dp[i] = Math.min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]);
}
return Math.min(dp[0],dp[1]);
}
}4. 解码方法
只有在 1 ~ 26 范围内的数字才可以解码，有前导 0 或者超过 26 的都不能解码
状态表示：以 i 位置为结尾时，解码方法的总数
此时就会有两种状态，s[i] 位置单独解码，s[i] 和 s[i - 1] 结合解码，每一种状态又可以分为解码成功和解码失败两种情况
状态转移方程：（根据最近的一步划分问题）根据情况来判断 dp[i] 是否加上 dp[i - 1] 和 dp[i - 2]
初始化：初始化 dp[0] 的时候也是有两种情况的，解码成功就是 1，解码失败就是 0，初始化 dp[1] 的时候就有三种情况了，由于是两个数字，所以就需要考虑两个单独解码和结合起来解码，如果都解码失败就是 0，如果单独解码成功就加 1，如果结合起来解码又成功了就再加上 1
填表顺序：从左往右
返回值：返回 dp[n - 1]
class Solution {
public int numDecodings(String s) {
int[] dp = new int[s.length()];
char[] chars = s.toCharArray();
if(chars[0]!='0'){
dp[0] = 1;
}
if(s.length() == 1) return dp[0];
if(chars[0]!='0'&&chars[1]!='0') dp[1] += 1;
int t = (chars[0] - '0') * 10 + chars[1] - '0';
if(t >= 10 && t <= 26) dp[1]+=1;
for(int i = 2;i < s.length();i++){
int tmp = (chars[i - 1] - '0') * 10 + chars[i] - '0';
if(chars[i] != '0') dp[i] += dp[i - 1];
if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
}
return dp[s.length() - 1];
}
}上面的代码的初始化过程看起来很麻烦，还可以优化一下：
上面初始化时是 dp[1] 比较麻烦的，可以把 dp 数组多开一个元素，
class Solution {
public int numDecodings(String s) {
int[] dp = new int[s.length() + 1];
char[] chars = s.toCharArray();
dp[0] = 1;
if(chars[0]!='0'){
dp[1] = 1;
}
if(s.length() == 1) return dp[1];
for(int i = 2;i <= s.length();i++){
int tmp = (chars[i - 2] - '0') * 10 + chars[i - 1] - '0';
if(chars[i - 1] != '0') dp[i] += dp[i - 1];
if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
}
return dp[s.length()];
}
}腾讯云开发者
