动态规划解斐波那契问题：三步、爬楼梯与解码方法

三步问题（面试题 08.01）

三步问题可以看作泰波那契的直接变种：小孩一次可以上1、2或3阶台阶，问走上第 n 阶有多少种走法。

这跟泰波那契几乎一致，只是初始值略有不同。设 dp[i] 表示走到第 i 阶的方法数，则 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。当 i=0 时，只有一种方式（原地不动）；i=1 时只有一种；i=2 时可以一步到顶或者分两步，共两种。因此初始化 dp[0]=1, dp[1]=1, dp[2]=2。注意题目要求结果对 1000000007 取模，因此在累加时就要取模，避免溢出。

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public int waysToStep(int n) {
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
        }
        return dp[n];
    }
}

使用最小花费爬楼梯（LeetCode 746）

这题不再是求方案数，而是求最小花费。给一个 cost 数组，cost[i] 表示从第 i 阶往上走需要支付的费用；可以从第0或第1阶开始，目标是到达楼顶（下标为 n，n = cost.length）。每次可以爬1或2阶。

这次 dp[i] 定义为到达第 i 阶的最小累计花费。那么到达 i 阶可以从 i-1 阶走一步，花费 dp[i-1] + cost[i-1]，或者从 i-2 阶走两步，花费 dp[i-2] + cost[i-2]。两者取最小。初始化时，从起点出发，dp[0]=0, dp[1]=0（因为可以选择从第0阶或第1阶开始，所以到达第0阶和第1阶本身不花费）。填表顺序从左到右，最后返回 dp[n]。

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n == 2) return Math.min(cost[0], cost[1]);
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

解码方法（LeetCode 91）

这道题稍微复杂一些，但状态转移依然只依赖于前两项。给出一个只含数字的字符串，编码规则是 126 分别对应字母 AZ，问有多少种不同的解码方式。

定义 dp[i] 为字符串前 i+1 个字符（索引 0..i）的解码方法数。对于当前位置 i，字符 s[i] 如果为 '1''9'，就可以单独解码，此时方案数加上 dp[i-1]；如果 s[i-1] 和 s[i] 组成的两位数在 1026 之间，则可以整体解码为一个字母，方案数再加上 dp[i-2]。初始化时要注意 '0' 开头的字符串直接返回 0。第一个位置单独判断，第二个位置同时判断单个和组合情况。

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int n = s.length();
        char[] ch = s.toCharArray();
        if (n == 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        if (ch[1] != '0' && ch[0] != '0') dp[1] += 1;
        int t = (ch[1] - '0') + (ch[0] - '0') * 10;
        if (t >= 10 && t <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            if (ch[i] != '0') dp[i] += dp[i - 1];
            t = (ch[i] - '0') + (ch[i - 1] - '0') * 10;
            if (t >= 10 && t <= 26) dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
}

这几道题都是线性 DP 里非常典型的「斐波那契式递推」问题。只要你把状态定义清楚，初始化填对，剩下的就是一路填表而已。空间优化可以滚动数组，但一般先写出完整的 dp 数组再优化会更不容易出错。