动态规划的核心，无非是定义状态、找到转移，再按顺序填表。很多问题都能套进一个类似斐波那契的递推结构中，比如泰波那契、爬楼梯、解码方法——它们都在dp[i]依赖于前几项的值，只是依赖的规则略有不同。
下面用四道 LeetCode 题目，看一下这个模型的几处变形。
第 N 个泰波那契数（LeetCode 1137）
题目要求：T0 = 0, T1 = 1, T2 = 1，且 Tn = Tn-1 + Tn-2 + Tn-3（n >= 3）。返回 Tn。
状态表示很直接：dp[i] 即第 i 个泰波那契数。转移方程即为dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。初始化前三个值，然后从左往右填即可。
// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
public int tribonacci(int n) {
if (n < 3) return n == 0 ? 0 : 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}
这里可以很容易优化空间，因为每次只用最近三个数。滚动数组的做法：
// 时间复杂度：O(N)
// 空间复杂度：O(1)
class Solution {
public int tribonacci(int n) {
if (n < 3) return n == 0 ? 0 : 1;
int[] dp = new int[]{0, 1, 1};
for (int i = 3; i <= n; i++) {
int tmp = dp[0];
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = tmp + dp[0] + dp[1];
}
return dp[2];
}
}
三步问题（面试题 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 数组再优化会更不容易出错。