动态规划经典题型：最小花费爬楼梯与解码方法

1. LeetCode 746. 使用最小花费爬楼梯

该题目难度较低，要求计算在可以一次走一步或者两步的情况下，到达结尾时的最小消耗。

状态表示为走到当前位置的最小消耗。

状态转移方程为 dp[i] = min(dp[i-1], dp[i-2]) + c[i]。

初始化时，第 0 个位置设为 c[0]，第 1 个位置设为 c[1]。这是因为状态转移依赖前两个位置的值。

填表顺序从前往后。

返回值为 dp 表最后两个位置的最小值。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& c) {
        int sz = c.size();
        vector<int> dp(sz + 1);
        dp[0] = c[0];
        dp[1] = c[1];
        for (int i = 2; i < sz; ++i) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + c[i];
        }
        return min(dp[sz - 1], dp[sz - 2]);
    }
};

2. LeetCode 91. 解码方法

该题给定一个字符串，不同的数字代表不同的字母，可单个或组合，求组成不同字母串的数量。