《算法题讲解指南：动态规划算法--斐波那契数列模型》--3.使用最小花费爬楼梯，4.解码方法

xiaoye-duck

490人浏览 · 2026-03-20 20:36:34

xiaoye-duck · 2026-03-20 20:36:34 发布

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
 《算法题讲解指南》--递归、搜索与回溯算法
 《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

3.使用最小花费爬楼梯

题目链接：

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

1.状态表示：
这道题可以根据「经验+题目要求」直接定义出状态表示：
第一种：以 i 位置为结尾，巴拉巴拉
dp[ i ]表示：到达位置时的最小花费。 (注意:到达 i 位置的时候，i 位置的钱不需要算上)

2.状态转移方程：
根据最近的一步，分情况讨论：
先到达 i - 1 的位置，然后支付 cost[ i - 1 ]，接下来走一步走到 i 位置：dp[ i - 1] + csot[ i - 1 ];
先到达 i - 2 的位置，然后支付 cost[ i - 2 ]，接下来走一步走到 i 位置：dp[ i - 2] + csot[ i - 2 ]。

3.初始化：
从我们的递推公式可以看出，我们需要先初始化 i = 0 ，以及 i = 1 位置的值。容易得到 dp[ 0 ] = dp[ 1 ] = 0 ，因为不需要任何花费，就可以直接站在第0层和第1层上。

4.填表顺序：
根据「状态转移方程」可得，遍历的顺序是「从左往右」。

5.返回值：
根据「状态表示以及题目要求」，需要返回dp[ n ]位置的值。

C++算法代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //1、创建 dp 表
        //2、初始化
        //3、填表
        //4、返回值
        int n = cost.size();
        vector<int> dp(n + 1);
        //dp[n-1]并不是登顶，dp[n-1]仍需要支付费用走到最后的dp[n]位置
        dp[0] = dp[1] = 0;
        //由于初始可以选择下标为 0 或下标为 1 的台阶开始
        //所以到达下标为 0 或下标为 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];
    }
};

算法总结及流程解析：

4.解码方法

题目链接：

91. 解码方法 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

类似于斐波那契数列~
1.状态表示：
根据以往的经验，对于大多数线性dp，我们经验上都是「以某个位置结束或者开始」做文章，这里我们继续尝试「用i位置为结尾」结合「题目要求」来定义状态表示。
dp[i]表示:字符串中[0，i]区间上，一共有多少种编码方法。

2.状态转移方程：
定义好状态表示，我们就可以分析i位置的dp值，如何由「前面」或者「后面」的信息推导出来。
关于i位置的编码状况，我们可以分为下面两种情况：
i.让i位置上的数单独解码成一个字母;
ii.让i位置上的数与i-1 位置上的数结合，解码成一个字母。
下面我们就上面的两种解码情况，继续分析：
(1)让i位置上的数单独解码成一个字母，就存在「解码成功」和「解码失败」两种情况：
i.解码成功：当i位置上的数在[1，9]之间的时候，说明i位置上的数是可以单独解码的，那么此时[0，i]区间上的解码方法应该等于[0，i-1]区间上的解码方法。因为[0，i-1]区间上的所有解码结果，后面填上一个i位置解码后的字母就可以了。此时dp[i]=dp[i-1]；
ii.解码失败:当i位置上的数是0的时候，说明i位置上的数是不能单独解码的，那么此时[0, i]区间上不存在解码方法。因为位置如果单独参与解码，但是解码失败了，那么前面做的努力就全部白费了。此时dp[i]=0。
(2)让i位置上的数与i-1位置上的数结合在一起，解码成一个字母，也存在「解码成功」和「解码失败」两种情况：
i.解码成功：当结合的数在[10，26]之间的时候，说明[i-1，i]两个位置是可以解码成功的，那么此时[0，i]区间上的解码方法应该等于[0，i-2]区间上的解码方法，原因同上。此时dp[i]=dp[i-2];
ii.解码失败:当结合的数在[0，9]和[27，99]之间的时候，说明两个位置结合后解码失败(这里一定要注意00 1 0203 4......这几种情况)，那么此时[0，i]区间上的解码方法就不存在了，原因依旧同上。此时dp[i]=0。
综上所述：dp[i]最终的结果应该是上面四种情况下，解码成功的两种的累加和(因为我们关心
的是解码方法，既然解码失败，就不用加入到最终结果中去)，因此可以得到状态转移方程(dp[i]默认初始化为0)
i.当s[i]上的数在[1，9]区间上时:dp[i]+=dp[i-1];
ii.当 s[i-1]与s[i]上的数结合后，在[10，26]之间的时候:dp[i]+=dp[i -2];
如果上述两个判断都不成立，说明没有解码方法，dp[i]就是默认值0。

3.初始化：
由于可能要用到i-1以及i-2 位置上的dp值，因此要先初始化「前两个位置」。
初始化dp[0]：
i. 当s[0]=='0'时，没有编码方法，结果dp[0]=0;
ii.当s[0] !='0'时，能编码成功，dp[0]=1
初始化dp[1]：
i.当s[1]在[1，9]之间时，能单独编码，此时dp[1]+=dp[0] (原因同上，dp[1]默认为0)
ii.当s[0]与s[1]结合后的数在[10，26]之间时，说明在前两个字符中，又有一种编码方式，此时dp[1]+=1

4.填表顺序：
根据「状态转移方程」可得，遍历的顺序是「从左往右」。

5.返回值：
应该返回 dp[n - 1] 的值，表⽰在 [0, n - 1] 区间上的编码方法。

C++算法代码：

class Solution {
public:
    int numDecodings(string s) 
    {
        //1、创建 dp 表
        //2、初始化
        //3、填表
        //4、返回值    
        int n = s.size();
        vector<int> dp(n, 0);
        //处理边界情况
        if(s[0] != '0')
        {
            dp[0] += 1;
        }
        if(n == 1)
        {
            return dp[0];
        }
        if(s[1] != '0')
        {
            dp[1] += dp[0];
        }
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if(t >= 10 && t <= 26)
        {
            dp[1] += 1;
        }
        //dp[i]表示第i个位置的解码方法总数
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0')
            {
                dp[i] += dp[i - 1];
            }
            int t = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if(t >= 10 && t <= 26)
            {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n - 1];
    }
};

C++算法代码(代码优化版本)：

class Solution {
public:
    int numDecodings(string s) 
    {
        //1、创建 dp 表
        //2、初始化
        //3、填表
        //4、返回值    
        int n = s.size();
        //代码优化：(由于上面单独讨论dp[1]的逻辑和循环内逻辑十分类似，所以可以考虑合并)
        //通过dp数组增加一位，将原dp数组的所有值全部往后挪动一位即可避免越界情况
        vector<int> dp(n + 1, 0);
        //处理边界情况
        if(s[0] != '0')
        {
            dp[1] += 1;
        }
        if(n == 1)
        {
            return dp[1];
        }

        dp[0] = 1;//虚拟值，下标0初始化为1的原因是对应上面的dp[1] += 1;
        //dp[i]表示第i个位置的解码方法总数
        for(int i = 2; i <= n; i++)
        {
            if(s[i - 1] != '0')
            {
                dp[i] += dp[i - 1];
            }
            int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            //由于原dp数组的值全部往后挪动一步，对于字符串s的下标映射关系也发生了变化：
            //s[i] ——> s[i - 1]，否则就会出现越界情况
            if(t >= 10 && t <= 26)
            {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

算法总结及流程解析：

结束语

到此，3.使用最小花费爬楼梯，4.解码方法这两道算法题就讲解完了。最小花费爬楼梯问题，通过状态转移方程dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])求解；解码方法问题，采用类似斐波那契的思路，考虑单独解码和组合解码两种情况。希望大家能有所收获！