动态规划

以 “1137.第 N 个泰波那契数” 为例总结动态规划模版1. 题目解析泰波那契数列定义如下T0 0 T1 1 T2 1当n 3时Tn Tn-1 Tn-2 Tn-3也就是说当前这一项由前面三项相加得到。例如T3 T2 T1 T0 1 1 0 2 T4 T3 T2 T1 2 1 1 4所以当n 4时答案是4。2. 动态规划思路动态规划一般可以按照下面几个步骤分析1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值2.1 状态表示定义一个dp数组dp[i] 表示第 i 个泰波那契数的值例如dp[0] 0 dp[1] 1 dp[2] 1 dp[3] 2 dp[4] 4这里的dp[i]不是表示下标本身而是表示第i项的答案。状态表示是什么可以简单的理解为dp 表里的值所表示的含义dp[i]状态表示怎么来1.题目要求本题dp[i] 表示第 i 个泰波那契数的值2.经验题目要求3.分析问题的过程中发现重复子问题2.2 状态转移方程根据题目定义Tn Tn-1 Tn-2 Tn-3所以可以得到dp[i] dp[i - 1] dp[i - 2] dp[i - 3]意思是当前状态 前一个状态 前两个状态 前三个状态例如dp[4] dp[3] dp[2] dp[1] 2 1 1 4本题的状态方程就是dp[i] dp[i - 1] dp[i - 2] dp[i - 3]2.3 初始化因为计算dp[i]需要用到前三项所以必须先确定前三个位置的值。​​​​​​本题的初始化dp[0] 0 dp[1] 1 dp[2] 1同时要注意边界情况如果 n 0直接返回 0 如果 n 1 或 n 2直接返回 12.4 填表顺序因为dp[i] 依赖 dp[i - 1]、dp[i - 2]、dp[i - 3]也就是说计算当前状态时前面的状态必须已经计算出来。所以本题填表顺序应该是从左到右也就是从3开始一直算到n。for i 3 到 n: dp[i] dp[i - 1] dp[i - 2] dp[i - 3]2.5 返回值题目要求返回第n个泰波那契数所以最终返回 dp[n]3. 普通动态规划代码class Solution { public int tribonacci(int n) { // 边界 if (n 0) { return 0; } if (n 1 || n 2) { return 1; } // 1.创建 dp 表 int[] dp new int[n 1]; // 2.初始化 dp[0] 0; dp[1] 1; dp[2] 1; // 3.填表 for (int i 3; i n; i) { dp[i] dp[i - 1] dp[i - 2] dp[i - 3]; } // 4.返回值 return dp[n]; } }4. 空间优化普通写法使用了一个dp数组空间复杂度是O(n)但是我们发现计算当前的dp[i]时只需要用到前三个数dp[i - 1] dp[i - 2] dp[i - 3]所以没有必要保存整个数组只需要保存最近的三个值即可。4.1 滚动变量思路假设a dp[i - 3] b dp[i - 2] c dp[i - 1]那么当前值就是d a b c计算完成后要把变量向前滚动a b b c c d也就是原来的 b 变成新的 a 原来的 c 变成新的 b 当前算出的 d 变成新的 c这样每次循环都只维护三个数。4.2 空间优化代码class Solution { public int tribonacci(int n) { if (n 0) { return 0; } if (n 1 || n 2) { return 1; } int a 0; int b 1; int c 1; for (int i 3; i n; i) { int d a b c; a b; b c; c d; } return c; } }5. 复杂度分析普通 dp 数组写法时间复杂度O(n) 空间复杂度O(n)因为需要从3遍历到n并且使用了一个长度为n 1的数组。滚动变量优化写法时间复杂度O(n) 空间复杂度O(1)因为仍然需要循环计算但是只用了固定的几个变量。6. 总结这道题是一个非常典型的动态规划入门题。重点是搞清楚dp[i] 表示什么在这道题中dp[i] 表示第 i 个泰波那契数的值然后根据题目给出的递推公式可以直接得到状态转移方程dp[i] dp[i - 1] dp[i - 2] dp[i - 3]因为当前值依赖前面的值所以填表顺序是从左到右。最后由于每次计算只需要前三个状态所以可以用滚动变量把空间从O(n)优化到O(1)。