【动态规划】斐波那契数列模型

动态规划的解题步骤

一、第 N 个泰波那契数

题目描述：

思路讲解：

本道题需要我们计算解第 n 个泰波那契数，泰波那契序列的定义为：T0=0，T1=1，T2=1，且对于 n >= 3 有 Tn = Tn-3 + Tn-2 + Tn-1，可通过存储前序结果避免重复计算，以下为具体思路：

1. 状态表示：dp[i] 表示第 i 个泰波那契数 Ti 的值
2. 状态转移方程：
   • 根据序列定义，对于 i >= 3，当前状态的值由前三个状态的值相加得到：
     dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
3. 初始化：
   • 根据序列的基础定义，初始化状态数组的前三个值：
     • dp[0] = 0（对应 T0=0）
     • dp[1] = 1（对应 T1=1）
     • dp[2] = 1（对应 T2=1）
4. 填写 DP 表：
   • 采用自底向上的计算顺序，从基础项开始逐步计算更大的 i：
     • 从 i=3 开始，依次计算到 i=n，每个 dp[i] 都基于已计算的 dp[i-3]、dp[i-2]、dp[i-1] 得出，确保子问题已先求解
5. 结果返回：
   • 当计算完 dp[n] 后，该值即为第 n 个泰波那契数，直接返回即可

编写代码：

class Solution {
public:
    int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
        
        vector<int> dp(n+1);

        dp[0] = 0 , dp[1] = dp[2] = 1;

        for(int i = 3 ; i <= n ; i++)
        {
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }

        return dp[n];
    }
};

二、三步问题

题目描述：

思路讲解：

本道题需要我们计算小孩有多少种上楼梯的方式，小孩上楼梯可一次走 1 阶、2 阶或 3 阶，求上 n 阶台阶的总方式数，问题可拆解为：上 n 阶台阶的方式数 = 上 n-1 阶的方式数（最后一步走 1 阶） + 上 n-2 阶的方式数（最后一步走 2 阶） + 上 n-3 阶的方式数（最后一步走 3 阶）。以下是具体思路：

1. 状态表示：dp[i] 表示上 i 阶台阶的不同方式总数。
2. 状态转移方程：
   • 根据问题拆解逻辑，对于 i >= 4，当前台阶的方式数由前三个台阶的方式数相加得到：
     • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
3. 初始化：
   • 根据实际走法确定基础台阶数的方式数：
     • dp[1] = 1（1 阶台阶只有 1 种方式：走 1 阶）
     • dp[2] = 2（2 阶台阶有 2 种方式：1+1 或 2）
     • dp[3] = 4（3 阶台阶有 4 种方式：1+1+1、1+2、2+1、3）
4. 填写 DP 表：
   • 采用自底向上的计算顺序，从最小台阶数向目标台阶数推进：
     • 从 i = 4 开始，依次计算到 i = n，每个 dp[i] 都基于已计算的 dp[i-1]、dp[i-2]、dp[i-3] 得出，确保子问题已先求解
5. 结果返回：
   • 当计算完 dp[n] 后，该值即为上 n 阶台阶的方式总数（已取模），直接返回即可

编写代码：

class Solution {
public:
    int waysToStep(int n) {
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;

        int dp[n+1];
        dp[1] = 1 , dp[2] = 2; dp[3] = 4;
        for(int i = 4 ; i <= n ; i++)
        {
            dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 + dp[i-3])% 1000000007;
        } 

        return dp[n];
    }
};

三、使用最小花费爬楼梯

题目描述：

思路讲解：
本道题需要我们计算达到楼梯顶部的最低花费，爬楼梯时可从第 0 阶或第 1 阶开始，每次支付当前台阶费用后可爬 1 阶或 2 阶，目标是到达楼梯顶部（第 n 阶，n 为 cost 数组长度）的最低总花费，问题可拆解为：到达第 i 阶的最低花费 = 到达前 1 阶的花费 + 当前台阶费用 与 到达前 2 阶的花费 + 当前台阶费用 中的最小值，以下是具体思路：

1. 状态表示：dp[i] 表示到达第 i 阶台阶的最低总花费
2. 状态转移方程：
   • 对于 i >= 2，到达第 i 阶的最低花费取决于前两个台阶的花费：
     • 若从第 i-1 阶爬 1 阶到达第 i 阶，花费为 dp[i-1] + cost[i-1]（cost[i-1] 是第 i-1 阶的费用）
     • 若从第 i-2 阶爬 2 阶到达第 i 阶，花费为 dp[i-2] + cost[i-2]（cost[i-2] 是第 i-2 阶的费用）
   • 因此转移方程为：
     • dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
3. 初始化：
   • 根据起始条件，从第 0 阶或第 1 阶开始时无需提前支付费用：
     • dp[0] = 0（到达第 0 阶的花费为 0）
     • dp[1] = 0（到达第 1 阶的花费为 0）
4. 填写 DP 表：
   • 采用自底向上的计算顺序，从低阶台阶向高阶台阶推进：
     • 从 i = 2 开始，依次计算到 i = n（楼梯顶部），每个 dp[i] 都基于已计算的 dp[i-1] 和 dp[i-2] 得出，确保子问题已先求解
5. 结果返回：
   • 楼梯顶部对应第 n 阶，因此 dp[n] 即为到达顶部的最低花费，直接返回即可

编写代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();

        vector<int> dp(n+1);
        dp[0] = 0 , dp[1] = 0;

        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];
    }
};

四、解码方法

题目描述：

思路讲解：
本道题需要我们计算解码方法的总数，解码规则为数字串可按 1-26 映射为字母，其中 “0” 无法单独解码，“01”-“09”、“27”+ 等也不合法，问题可拆解为：前 i 个字符的解码数 = 前 i-1 个字符的解码数（若第 i 个字符合法） + 前 i-2 个字符的解码数（若第 i-1 和 i 个字符组成的两位数合法）。以下是具体思路：

1. 状态表示：dp[i] 表示字符串 s[0…i]（前 i+1 个字符）的解码方法总数
2. 状态转移方程：
   • 对于 i >= 2，当前位置的解码数取决于两种可能的拆分方式：
     • 单字符解码：若 s[i] != ‘0’（单个数字合法），则 dp[i] += dp[i-1]（累加前 i-1 个字符的解码数）
     • 双字符解码：若 s[i-1] 和 s[i] 组成的两位数 num 满足 10 <= num <= 26（两位数合法），则 dp[i] += dp[i-2]（累加前 i-2 个字符的解码数）
   • 因此转移方程为：
     • dp[i] = （单字符合法时的 dp[i-1]） + （双字符合法时的 dp[i-2]）
3. 初始化：
   • 第一个字符：dp[0] = 1 若 s[0] != ‘0’（单个非零数字可解码），否则为 0（“0” 无法解码）
   • 第二个字符：
     • 若前两个字符组成的两位数 10 <= num <= 26，则 dp[1] += 1（作为双字符解码）
     • 若第二个字符 s[1] != ‘0’，则 dp[1] += dp[0]（作为单字符解码，累加第一个字符的解码数）
     • 若字符串长度为 1，则直接返回 dp[0]
4. 填写 DP 表：
   • 采用自底向上的计算顺序，从第三个字符开始逐步推进：
     • 从 i = 2 遍历到 i = n-1，对每个位置分别判断单字符和双字符的合法性，按转移方程累加解码数
5. 结果返回：
   • 整个字符串的解码方法总数存储在 dp[n-1] 中（n 为字符串长度），直接返回即可

通过观察下面的代码，发现dp[1]的初始化和后序转移方程是一样的，这里就对初始化进行优化：

• 将dp表整体向后移动一格，引入一个虚拟节点，dp[i]直接表示前i个字符（s[0…i-1]）的解码数
• 设dp[0] = 1（空字符串解码数为 1，作为双字符解码的基础状态），dp[1]直接对应第一个字符的合法性
• 取消i=1的特殊处理，对所有 i >= 2 采用相同逻辑

编写代码：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();

        vector<int>dp(n,0);
        dp[0] = s[0] == '0' ? 0 : 1;
        if(n == 1) return dp[0];

        int num = (s[0] - '0') * 10 + (s[1] - '0');
        if(num >= 10 && num <= 26) dp[1] = 1;
        if(s[1] != '0') dp[1] += dp[0];

        for(int i = 2 ; i < n ; i++)
        {
            num = (s[i-1] - '0')* 10 + s[i] - '0'; 
            if(num >= 10 && num <= 26) dp[i] += dp[i-2];
            if(s[i] != '0') dp[i] += dp[i-1];
        }

        return dp[n-1];
    }
};

// 优化初始化
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();

        vector<int>dp(n+1,0);
        dp[0] = 1;
        dp[1] = s[1-1] == '0' ? 0 : 1;

        for(int i = 2 ; i <= n ; i++)
        {
            int num = (s[i-2] - '0')* 10 + s[i-1] - '0'; 
            if(num >= 10 && num <= 26) dp[i] += dp[i-2];
            if(s[i-1] != '0') dp[i] += dp[i-1];
        }

        return dp[n];
    }
};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹