动态规划的步骤：
- 状态表示。所谓状态表示就是 dp 表里的值表示什么含义，那么状态表示怎么找呢？
- 题目要求
- 经验（以某一个位置为结尾 / 起点） + 题目要求
- 分析问题的过程中发现重复子问题
- 状态转移方程。dp[ i ] 等于什么
- 初始化。保证填表的时候不越界
- 填表顺序。保证填写当前状态时，所需要的状态已经计算过了，初始化之后，下标的映射关系要一致
- 返回值。根据题目要求和状态表示进行返回
1. 第 N 个泰波那契数
这题比较简单，直接秒了
状态表示：dp[i] 表示第 i 个泰波那契数的值
状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
初始化：把前三个数初始化
填表顺序：从左到右
返回值：返回 dp[n]
class Solution { public int tribonacci(int n) { int[] dp = new int[38]; dp[0] = 0; dp[1] = 1; dp[2] = 1; if(n < 3){ return dp[n]; } for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } return dp[n]; } }
还可以对上述代码进行空间优化，因为在求第 i 个位置的时候，只需要知道前三个数即可，每次求一个位置都是这样，所以就可以定义三个变量，不断地更新，实现滚动数组的效果
滚动数组空间优化版本：
class Solution { public int tribonacci(int n) { int sum = 0; int a = 0,b = 1,c = 1; if (n == 0) return 0; if (n == 1 || n == 2) return 1; for (int i = 3; i <= n; i++) { sum = a + b + c; a = b; b = c; c = sum; } return sum; } }
2. 面试题 08.01. 三步问题
状态表示：dp[i] 表示到达第 i 个位置时的方案数
状态转移方程： dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
初始化：计算前三个数的方案数，把前三个数初始化
填表顺序：从左到右
返回值：返回 dp[n]
class Solution { public int waysToStep(int n) { long a = 1,b = 2,c = 4; if(n == 1) return 1; if(n == 2) return 2; if(n == 3) return 4; long res = 0; for(int i = 4;i <= n;i++){ res = (a + b + c) % 1000000007; a = b; b = c; c = res; } return (int) res; } }
3. 使用最小花费爬楼梯
状态表示：dp[i] 表示到达第 i 个位置时的最小花费
状态转移方程：
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
初始化：由于需要用到前两个数，所以需要把 dp[0] 和 dp[1] 初始化，因为刚开始可以直接从 0 下标或 1 下标出发，所以可以初始化为 0
填表顺序：从左到右
返回值：返回 dp[n]，楼梯顶部为 n 下标，也就是
Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2])
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n]; if (n == 1 ) return 0; if(n == 2) return Math.min(cost[0],cost[1]); dp[0] = 0; dp[1] = 0; for (int i = 2; i < n; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]); } }
还有第二种状态表示可以解决：
dp[i] 表示从 i 位置出发，到达楼顶的最小花费
初始化：用这种方法的话，就需要用到后面两个元素，所以刚开始初始化需要把最后的两个元素初始化
初始 dp[n - 1] 时就表示从 n - 1 位置支付 cost[n - 1] 就可以直接到达楼顶，dp[n - 2] 时支付 cost[n - 2] 也可以直接到达楼顶
填表顺序：从后往前
最后的返回值也就是 dp[0] 和 dp[1] 的最小值
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n]; if (n == 1 ) return 0; if(n == 2) return Math.min(cost[0],cost[1]); dp[n - 1] = cost[n - 1]; dp[n - 2] = cost[n - 2]; for(int i = n - 3;i >= 0;i--){ dp[i] = Math.min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]); } return Math.min(dp[0],dp[1]); } }
4. 解码方法
只有在 1 ~ 26 范围内的数字才可以解码，有前导 0 或者超过 26 的都不能解码
状态表示：以 i 位置为结尾时，解码方法的总数
此时就会有两种状态，s[i] 位置单独解码，s[i] 和 s[i - 1] 结合解码，每一种状态又可以分为解码成功和解码失败两种情况
状态转移方程：（根据最近的一步划分问题）根据情况来判断 dp[i] 是否加上 dp[i - 1] 和 dp[i - 2]
初始化：初始化 dp[0] 的时候也是有两种情况的，解码成功就是 1，解码失败就是 0，初始化 dp[1] 的时候就有三种情况了，由于是两个数字，所以就需要考虑两个单独解码和结合起来解码，如果都解码失败就是 0，如果单独解码成功就加 1，如果结合起来解码又成功了就再加上 1
填表顺序：从左往右
返回值：返回 dp[n - 1]
class Solution { public int numDecodings(String s) { int[] dp = new int[s.length()]; char[] chars = s.toCharArray(); if(chars[0]!='0'){ dp[0] = 1; } if(s.length() == 1) return dp[0]; if(chars[0]!='0'&&chars[1]!='0') dp[1] += 1; int t = (chars[0] - '0') * 10 + chars[1] - '0'; if(t >= 10 && t <= 26) dp[1]+=1; for(int i = 2;i < s.length();i++){ int tmp = (chars[i - 1] - '0') * 10 + chars[i] - '0'; if(chars[i] != '0') dp[i] += dp[i - 1]; if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2]; } return dp[s.length() - 1]; } }
上面的代码的初始化过程看起来很麻烦，还可以优化一下：
上面初始化时是 dp[1] 比较麻烦的，可以把 dp 数组多开一个元素，
class Solution { public int numDecodings(String s) { int[] dp = new int[s.length() + 1]; char[] chars = s.toCharArray(); dp[0] = 1; if(chars[0]!='0'){ dp[1] = 1; } if(s.length() == 1) return dp[1]; for(int i = 2;i <= s.length();i++){ int tmp = (chars[i - 2] - '0') * 10 + chars[i - 1] - '0'; if(chars[i - 1] != '0') dp[i] += dp[i - 1]; if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2]; } return dp[s.length()]; } }
这一题和珠宝最大和是非常相似的，不过就是这里要求最小的路径和
状态表示：dp[i][j] 表示到达 (i , j) 时的最小路径和
状态转移方程：
初始化：
返回值：dp[m][n]
class Solution { public int minPathSum(int[][] grid) { int m = grid.length,n = grid[0].length; int[][] dp = new int[m + 1][n + 1]; for(int i = 0;i < m + 1;i++){ for(int j = 0;j < n + 1;j++){ dp[i][j] = Integer.MAX_VALUE; } } dp[1][0] = dp[0][1] = 0; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ dp[i+1][j + 1] = Math.min(dp[i + 1][j],dp[i][j+1]) + grid[i][j]; } } return dp[m][n]; } }
