【动态规划之斐波那契数列模型】——累加递推型动态规划

第N个泰波那契数列

解题思路： 泰波那契数列的第 N 项定义为前面三项之和，即 T0 = 0, T1 = 1, T2 = 1，从 T3 开始，每一项都等于前三项的和。要找到第 N 项，可以使用动态规划逐步求解每个值直到 TN。

初始化 T0 = 0, T1 = 1, T2 = 1。
使用一个数组或三个变量记录最近三项的值。
从 T3 开始，利用递推公式 Tn = T(n-1) + T(n-2) + T(n-3) 计算到第 N 项。
返回结果。
时间复杂度为 O(n)，空间复杂度为 O(1)（若只保留最近三项值）。

class Solution 
{
public:int tribonacci(int n) {// 如果 n 等于 0，直接返回 0，因为 T0 = 0if(n == 0) return 0;// 如果 n 等于 1 或 2，返回 1，因为 T1 = T2 = 1if(n == 1 || n == 2) return 1;// 初始化前三项的值int a = 0, b = 1, c = 1, d = 0;// 从第 3 项开始计算到第 n 项for(int i = 3; i <= n; i++){// 当前项 d 是前面三项的和d = a + b + c;// 更新前三项的值，将 a, b, c 滚动到下一个位置a = b; // 原 b 变成新的 ab = c; // 原 c 变成新的 bc = d; // 当前项 d 变成新的 c}// 返回第 n 项的值return d;}
};

class Solution 
{
public:int tribonacci(int n) { // 特殊情况处理if(n == 0) return 0;   // 当 n 为 0 时，返回 0if(n == 1 || n == 2) return 1;  // 当 n 为 1 或 2 时，返回 1// 定义 dp 数组，dp[i] 表示第 i 个泰波那契数vector<int> dp(n + 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];  // 当前项等于前三项之和}// 返回第 n 项的泰波那契数return dp[n];}
};

面试题08.01.三步问题

解题思路： 在楼梯上每次可以选择走 1 步、2 步或 3 步，问走到第 n 级台阶有多少种不同的方法。这个问题可以看作一个动态规划问题。

定义 dp[i] 为到达第 i 级台阶的方法总数。
基础条件：dp[0] = 1（在起点不动算一种方法），dp[1] = 1，dp[2] = 2。
递推公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，因为可以从前一、前二或前三个台阶到达。
从小到大依次计算 dp[i]，最终得到 dp[n]。
时间复杂度为 O(n)，空间复杂度也为 O(1)（只需记录前几项的值）。

class Solution 
{
public:int waysToStep(int n) {// 定义取模常量，用于防止结果过大const int MOD = 1e9 + 7;// 定义 dp 数组，dp[i] 表示到达第 i 级台阶的方法数vector<int> dp(n + 1);// 处理特殊情况if(n == 1 || n == 2) return n; // 如果 n 是 1 或 2，直接返回 nif(n == 3) return 4;           // 如果 n 是 3，直接返回 4（方法有：1+1+1, 1+2, 2+1, 3）// 初始化前三个台阶的方法数dp[1] = 1;  // 到达第 1 级台阶只有 1 种方法dp[2] = 2;  // 到达第 2 级台阶有 2 种方法：1+1 或 2dp[3] = 4;  // 到达第 3 级台阶有 4 种方法：1+1+1, 1+2, 2+1, 3// 从第 4 级台阶开始，使用递推公式计算每一级台阶的方法数for(int i = 4; i <= n; i++){// 当前台阶的方法数等于前一、前二和前三个台阶的方法数之和，并对 MOD 取模dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}// 返回到达第 n 级台阶的方法数return dp[n];}
};

使用最小花费爬楼梯

解题思路： 每一步都有一个代价，从楼梯底部出发，最终要到达顶层。选择以最小代价到达顶层。

定义 dp[i] 为到达第 i 层的最小花费。
初始状态：dp[0] = cost[0]，dp[1] = cost[1]。
递推公式：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]，即可以从前一层或前两层到达。
为了达到顶层，我们可以从 n-1 或 n-2 层爬上去，所以最终答案是 min(dp[n-1], dp[n-2])。
优化：我们可以仅用两个变量记录前两个状态值，进一步降低空间复杂度到 O(1)。

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();// 定义 dp 数组，dp[i] 表示从第 i 级台阶出发到达楼顶的最小花费vector<int> dp(n);// 初始化最后两个台阶的花费dp[n - 1] = cost[n - 1]; // 从最后一级直接到达顶层的花费就是 cost[n-1]dp[n - 2] = cost[n - 2]; // 从倒数第二级直接到达顶层的花费就是 cost[n-2]// 从倒数第三个台阶开始向前计算每一级的最小花费for(int i = n - 3; i >= 0; i--){// 当前台阶的最小花费等于当前台阶的成本加上从下一阶或下下阶出发的最小花费dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);} // 返回从第 0 或第 1 个台阶出发的较小花费，因为可以从这两级开始攀登return min(dp[0], dp[1]);}
};

解码问题

解题思路： 给定一个数字字符串，按字母表中的编码规则解码出不同的解码方式数量（如 A=1，B=2，… Z=26）。

定义 dp[i] 为长度为 i 的子字符串的解码方式数。
初始状态：dp[0] = 1（空字符串有一种解码方式，即不解码）。
递推公式：
若 s[i-1] 是一个有效的单个字符（非 0），则 dp[i] += dp[i-1]。
若 s[i-2:i] 是有效的双字符（10 到 26），则 dp[i] += dp[i-2]。
最终结果为 dp[n]，即整个字符串的解码方式数。
该算法的时间复杂度为 O(n)，空间复杂度也可以优化到 O(1)。

class Solution 
{
public:int numDecodings(string s) {int n = s.size();// 定义 dp 数组，dp[i] 表示长度为 i 的子字符串的解码方法总数vector<int> dp(n + 1);// 初始状态：空字符串有一种解码方法dp[0] = 1;// dp[1] 取决于第一个字符是否为 '0'，如果是 '0' 则没有解码方法dp[1] = s[0] != '0';// 从第二个字符开始遍历，逐步计算解码方法数for(int i = 2; i <= n; i++){// 处理单独解码的情况，如果当前字符不为 '0'，则可以单独解码if(s[i - 1] != '0') dp[i] += dp[i - 1];// 处理两个字符组合解码的情况int a = (s[i - 2] - '0') * 10 + (s[i - 1] - '0'); // 计算当前和前一个字符组合的数值if(a >= 10 && a <= 26) dp[i] += dp[i - 2];}// 返回整个字符串的解码方法总数return dp[n];}
};