动态规划——斐波那契数列模型问题
文章目录
- 1137. 第 N 个泰波那契数
- 算法原理
- 代码实现
- 面试题 08.01. 三步问题
- 算法原理
- 代码实现
- 746. 使用最小花费爬楼梯
- 算法原理
- 代码实现
- 91. 解码方法
- 算法原理
- 代码实现
1137. 第 N 个泰波那契数
题目链接：1137. 第 N 个泰波那契数
算法原理
-
状态表示：
根据题目要求可得出 -
状态转移方程：
也是根据题目得出dp[i]依赖前三个状态dp[i] = dp[i-1] + dp[i-2] + dp[i-3] -
初始化：
保证填表不越界，根据题目可以得出dp[0] = 0; dp[1] = dp[2] = 1; -
填表顺序：
根据前面的状态，计算当前状态
从左向右 -
返回值：
dp[i]
代码实现
class Solution {
public:
int tribonacci(int n)
{
if(n == 0) return 0;
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];
}
};
这里可以用空间优化，求当前状态的时候，只依赖前面3个状态。
用滚动数组：
class Solution { public: int tribonacci(int n) { if(n == 0) return 0; if(n == 1 || n == 2) return 1; int a = 0, b = 1, c = 1, d = 0; for(int i = 3; i <= n; i++) { d = a + b + c; a = b; b = c; c = d; } return d; } };
面试题 08.01. 三步问题
题目链接：面试题 08.01. 三步问题
-
到1号位置：1种方法（起始位置上2个台阶）
-
到2号位置：
起始位置直接上2阶
1号位置上1阶（经过1号一种方法）
1+1 = 2种方法 -
到3号位置
从起始位置上3阶
1号位置上2阶（经过1号一种方法）
2号位置上1阶（经过2号两种方法）1 + 1 + 2 = 4种方法
-
到4号位置
从1号位置上3阶（经过1号一种方法）
从2号位置上2阶（经过2号两种方法）
从3号位置上1阶（经过3号4种方法）
1 + 2 + 4 = 7种方法
之后就是同理…
算法原理
-
状态表示：
到达i号台阶一共有多少种方法 -
状态转移方程：
以i位置最近的一步（三种，因为可以跨1、2、3阶）
即dp[i] = dp[i-3] + dp[i-2] + dp[i-1] -
初始化：
一个状态依赖前3个状态，刚刚上面推出了dp[1] = 1; dp[2] = 2; dp[3] = 4; -
填表顺序：
从左往右 -
返回值：
dp[i]
代码实现
class Solution {
public:
int waysToStep(int n)
{
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
vector<int> dp(n + 1);
int MOD = 1e9 + 7;
//初始化
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
//到达i台阶有多少种方法
for(int i = 4; i <= n; i++)
{
//上台阶3种, 选取最近一步划分
//i-1 i-2 i-3
dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
}
return dp[n];
}
};
746. 使用最小花费爬楼梯
题目链接：746. 使用最小花费爬楼梯
题目有一个要注意的，到达楼梯顶，并不是数组末尾元素，而是在末尾元素的下一个位置
算法原理
-
状态表示：
以xx位置为结尾，xxx（题目要求）
这里的xxx就是到达i位置的最小花费
-
状态转移方程：
以i位置最近的一步（两种，因为可以跨1、2阶）
即dp[i] = min(dp[i-2]+cost[i-2], dp[i-1] + cost[i-1]) -
初始化(保证填表不越界)：
dp[0] = dp[1] = 0; dp[2] = 2; dp[3] = 4; -
填表顺序：
从左往右 -
返回值：
dp[i]
代码实现
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
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. 解码方法
题目链接：91. 解码方法
算法原理
- 状态表示：
以某个位置为结尾，xxx
即dp[i]表示以i位置为结尾，解码方法的总数 - 状态转移方程：
根据最近一步，划分问题
- 初始化：
一个状态依赖前2个状态
- 填表顺序：
从左往右 - 返回值：
dp[i-1]
代码实现
class Solution {
public:
int numDecodings(string s)
{
int n = s.size();
vector<int> dp(n);
dp[0] = s[0] != '0';
if(n == 1) return dp[0];
if(s[0] != '0' && s[1] != '0')
{
dp[1] += 1;
}
int cmb = (s[0]-'0')*10 + (s[1]-'0');
if(cmb >= 10 && cmb <= 26)
{
dp[1] += 1;
}
for(int i = 2; i < n; i++)
{
if(s[i] != '0')
{
dp[i] += dp[i-1];
}
cmb = (s[i-1]-'0')*10 + (s[i]-'0');
if(cmb >= 10 && cmb <= 26)
{
dp[i] += dp[i-2];
}
}
return dp[n-1];
}
};
代码优化：
为什么虚拟节点可以填1？ 因为在原始的0和1位置拼接起来，要是能解码成功，说明找到了一种解码方式，是要加上dp[0]的值，如果dp[0]为0的话，就相当于忽略掉了。
class Solution { public: int numDecodings(string s) { int n = s.size(); vector<int> dp(n+1); dp[0] = 1; dp[1] = s[0] != '0'; for(int i = 2; i <= n; i++) { if(s[i-1] != '0') { dp[i] += dp[i-1]; } int cmb = (s[i-2]-'0')*10 + (s[i-1]-'0'); if(cmb >= 10 && cmb <= 26) { dp[i] += dp[i-2]; } } return dp[n]; } };
