动态规划五步骤：

  1. 认识dp数组的索引含义
  2. 寻找递推公式
  3. dp数组初始化
  4. 寻找遍历顺序
  5. 打印dp数组

题型一：

打家劫舍

image.png
思路：
递归：
当我们计算如果有n家可以偷的房屋时，我们从最后一家开始看起，偷最后一家后的最大金额考虑是：
1.我们偷第n家，这时第n-1家不可以偷，所以最大金额是前n-2家最大的值加上第n家的金额。
2.我们不偷第n家，这时第n-1家可以偷，所以最大金额就是前n-1家能偷的最大值。

边界条件是：
1.一家都没有，返回0。
2.有一家能偷，返回此家能偷的钱。
3.有两家能偷，返回这两家最大的钱。

代码：

  1. var rob = function(nums) {
  2.     function cal(n){
  3.     if(n==0)return 0;
  4.     if(n==1)return nums[0];
  5.     if(n==2)return Math.max(nums[0],nums[1]);
  6.     if(n>2)return Math.max(cal(n-1),cal(n-2)+nums[n-1]);
  7. }
  8.     return cal(nums.length);
  10. };

代码是我自己写的，很不幸的是它超时了。。。
image.png
这时我们来看官方给出的答案：

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  6.         int length = nums.length;
  7.         if (length == 1) {
  8.             return nums[0];
  9.         }
  10.         int[] dp = new int[length];
  11.         dp[0] = nums[0];
  12.         dp[1] = Math.max(nums[0], nums[1]);
  13.         for (int i = 2; i < length; i++) {
  14.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  15.         }
  16.         return dp[length - 1];
  17.     }
  18. }

官方没有JS的答案，不过思路都是一样的，就是用一个数组来保存状态从而避免递归的使用。
所以我重写了一下：

  1. var rob = function(nums) {
  2.     if(nums.length == 0||nums==null)return 0;
  3.     if(nums.length == 1) return nums[0];
  4.     var dp = new Array();
  5.     dp[0] = nums[0];
  6.     dp[1] = Math.max(nums[0],nums[1]);
  7.     for(let i = 2;i<nums.length;i++){
  8.         dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
  9.     }
  10.     return dp[nums.length-1];
  11. };

结果：
image.png
题型二：

三角形最小路径和

image.png
思路：
遍历行列，计算每个数据的最小路径，用二维数组记录，通过动态规划来得到最小值。最后再遍历一遍最后一行的数据，把最小的值返回。和上一题思路差不多，不过动用到二维数组相对复杂一点。

  1. var minimumTotal = function(triangle) {
  2.     if(triangle.length==0||triangle==null)return 0;
  3.     if(triangle.length == 1)return triangle[0][0];
  4.     let length = triangle.length;
  5.      let len = triangle.length
  6.        let len2 = triangle[len - 1].length
  7.           let dp = new Array(len).fill('').map(item => new Array(len2))//创建二维数组
  8.     dp[0][0] = triangle[0][0];
  9.     dp[1][0] = dp[0][0]+triangle[1][0];
  10.     dp[1][1] = dp[0][0]+triangle[1][1];
  11.     for(let i = 2;i<length;i++){
  12.         dp[i][0] = dp[i-1][0]+triangle[i][0];//计算第一个的dp
  13.         for(let j = 1;j<i;j++){
  14.             dp[i][j] = Math.min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]);
  15.         }
  16.         dp[i][i] = dp[i-1][i-1]+triangle[i][i];//计算最后一个的dp
  17.     }
  18.     var out = dp[length-1][0];
  19.     for(let i =1;i<dp[length-1].length;i++){
  20.         out = Math.min(out,dp[length-1][i]);
  21.     }
  22.     return out;
  23. };

提交结果：
image.png
这个结果明显很差劲啊，我们来看看更好的解法。

  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int>>& triangle) {
  4.         vector<int> dp(triangle.back());
  5.         for(int i = triangle.size() - 2; i >= 0; i --)
  6.             for(int j = 0; j <= i; j ++)
  7.                 dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
  8.         return dp[0];
  9.     }
  10. };

这是自下而上的算法，triangle.back是取triangle最后一行来给dp初始化的，通过遍历，最小的数值最终会落到dp[0]里面。

题型三：

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  1. #include <iostream>
  2. using namespace std;
  3. int res[100];
  4. int tmp = 1000000007;
  5. int Max = 2;
  6. int dp(int n){
  7.     if(n <= Max){
  8.         return res[n];//如果有存储就直接返回结果
  9.     }
  10.     else{    
  11.         res[n] = (dp(n-1) + dp(n-2))%tmp;//动态规划
  12.         Max = n;
  13.     }
  14.     return res[n];
  15. } 
  16. int main(){
  17.     int n;
  18.     res[0] = 0;
  19.     res[1] = 1;
  20.     res[2] = 2;//前三级台阶
  21.     while(cin>>n){
  22.         //一旦有输入就输出结果
  23.         cout<<dp(n)<<endl;
  24.     }
  25.     return 0;
  26. }