【算法】动态规划专题一 斐波那契数列模型 1-4

1.第N个泰波那契数

1.1 题目

题目链接

2. 代码

// 代码1：时间复杂度O(N) 空间复杂度O(N)
class Solution {
public:int tribonacci(int n) {// 1. 判断边界条件if(n == 0) return 0;if(n == 1 || n == 2) return 1;// 2. 建立dp表vector<int> dp(n + 1);// 3. 初始化dp[0] = 0, dp[1] = dp[2] = 1;// 4. 填表 转移方程 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] for(int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];// 5. 返回值return dp[n];  }
};

// 代码2：时间复杂度 O(N) 空间复杂度O(1)
class Solution {
public:int tribonacci(int n) {// 1. 判断边界条件if(n == 0) return 0;if(n == 1 || n == 2) return 1;// 2. 建立dp表vector<int> dp(n + 1);// 3. 初始化int a = 0, d = 0, b = 1, c = 1;// 4. 填表 转移方程 d = c + a for(int i = 3; i <= n; i++){d = c + b + a;a = b; b = c; c = d;}// 5. 返回值return d;  }
};

2. 三步问题

2.1 题目

题目

2.2 思路

2.3 代码

class Solution {
public:int waysToStep(int n) {if (n == 1 || n == 2) return n;if(n == 3) return 4;vector<int> dp(n + 1);int MOD = 1e9 + 7;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.leetcode 746.使用最小花费爬楼梯

3.1 题目

题目链接

3.2 思路

3.3 代码

// 解法1 从前向后填表
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];}
};

// 解法二 从后向前填表
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(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.leetcode 91.解码方法

4.1 题目

题目链接

4.2 思路

4.3 代码

// 代码1 未优化初始化部分
class Solution {
public:int numDecodings(string s) {// 创建dp表// 初始化// 填表// 返回值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 k1 = (s[0] - '0') * 10 + s[1] - '0'; // 前两个位置合起来表示的数//if(10 <= k1 <= 26) dp[1] += 1; // 这种写法在C++中是错误的if(k1 >=10 && k1 <= 26) dp[1] += 1;for(int i = 2; i < n; i++){if(s[i] != '0') dp[i] += dp[i - 1];int k2 = (s[i - 1] - '0') * 10 + s[i] - '0'; //if(10 <= k2 <= 26) dp[i] += dp[i - 2];if(k2 >= 10 && k2 <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
};

class Solution {
public:int numDecodings(string s) {// 优化int n = s.size();vector<int> dp(n + 1);// 处理边界情况dp[0] = 1; // 保证后面的填表是正确的dp[1] = s[1 - 1] != '0';for(int i = 2; i <= n; i++){if(s[i - 1] != '0') dp[i] += dp[i - 1];int k = (s[i - 1 - 1] - '0') * 10 + s[i - 1] - '0'; if(k >= 10 && k <= 26) dp[i] += dp[i - 2];}return dp[n];}
};