理论基础

• 动态规划-DP

  1. 动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

  2. 背包问题：
     动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
     但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

• 动规五步

  1. 确定dp数组（dp table）以及下标的含义

  2. 确定递推公式

  3. dp数组如何初始化

  4. 确定遍历顺序

  5. 举例推导dp数组

509. 斐波那契数

• 解题思路：
  1.确定递推公式 => dp[i] = dp[i - 1] + dp[i - 2];
  2.确定遍历顺序 => 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，
  那么遍历的顺序一定是从前到后遍历的
  3.举例推导dp数组

public int fib(int n) {if(n <= 1){return n;}int[] dp = new int[2];dp[0] = 0;dp[1] = 1;int sum = 0;for (int i = 2; i <= n; i++) {sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum; }return sum;
}

70. 爬楼梯

• 解题思路：
  ①确定dp数组：dp[i]： 爬到第i层楼梯，有dp[i]种方法
  ②递推公式：dp[i] = dp[i - 1] + dp[i - 2]，dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法；
  dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法
  在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏
  ③初始化：不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义
  ④遍历顺序：从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

public int climbStairs(int n) {if(n <= 1){return n;}//dp数组int[] dp = new int[n + 1];//初始化dp[1] = 1;dp[2] = 2;//遍历for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

746. 使用最小花费爬楼梯

• 解题思路：
  1.dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
  2.确定递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]
  dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  3.dp数组如何初始化， dp[0] = 0，dp[1] = 0; 到达 第 0 个台阶是不花费的
  4.确定遍历顺序，从前向后遍历

public int minCostClimbingStairs(int[] cost) {//不用加判断// if(cost.length == 2){//     return 0;// }//注意：最后一步也要花费//dp数组int[] dp = new int[cost.length + 1];//初始化dp[0] = 0;dp[1] = 0;//遍历for (int i = 2; i <= cost.length; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.length];
}