day38

1、动规理论基础

1. 动态规划中每一个状态一定是由上一个状态推导出来的，而贪心是局部直接选最优的。
2. 解题步骤
   1. 确定dp数组（dp table）以及下标的含义
   2. 确定递推公式
   3. dp数组如何初始化
   4. 确定遍历顺序
   5. 举例推导dp数组

2、leetcode509 斐波那契数

1. 思路

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

      • dp[i] : 第i个数的斐波那契数值

   2. 确定递推公式

      • dp[i] = dp[i-1] + dp[i-2]

   3. dp数组如何初始化

      • dp[0] = 0

      • dp[1] = 1

   4. 确定遍历顺序

      • 后面的数值由前面的数值推导而得 ====》 从前往后遍历

   5. 举例推导dp数组

2. 代码

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

3. 递归法

   class Solution {
       public int fib(int n) {
           if(n <= 1) {
               return n;
           }
           return fib(n-1) + fib(n-2);
       }
   }
   

3、leetcode70 爬楼梯

1. 思路

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

      • dp[i] : 爬到第i阶楼梯的方法数量

   2. 确定递推公式

      • dp[i] = dp[i-1] + dp[i-2]

      • 因为每次可以爬1或2个台阶 ===》因此，第i阶可从第i-1阶爬1阶到达，也可从第i-2阶爬2阶到达

      • 因此，爬到第i阶楼梯的方法数量 = 爬到第i-1阶楼梯的方法数量 + 爬到第i-2阶楼梯的方法数量

   3. dp数组如何初始化

      • dp[1] = 1

      • dp[2] = 2

   4. 确定遍历顺序

      • 后面的数值由前面的数值推导而得 ====》 从前往后遍历

   5. 举例推导dp数组

2. 代码

   class Solution {
       public int climbStairs(int n) {
           if(n <= 2) return n;
   
           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];
       }
   }
   

4、leetcode746 使用最小花费爬楼梯

1. 思路

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

      • dp[i] ： 爬到第i阶需要的最低花费
      • 已知cost[i] ：从第i阶向上爬需要支付的费用
      • 总阶梯数 = cost[].length

   2. 确定递推公式

      • dp[i] = min(dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2] )
      • 因为每次可以爬1或2个台阶 ===》因此，第i阶可从第i-1阶爬1阶到达，也可从第i-2阶爬2阶到达【先到达i-1阶，再从第i-1阶向上爬】【dp[i-1] + cost[i-1]】

   3. dp数组如何初始化

      • 已知可从下标为 0 或下标为 1 的台阶开始爬楼梯。 ==》达到下标为 0 或下标为 1 的台阶不要花费

      • dp[0] = 0

      • dp[1] = 0

   4. 确定遍历顺序

      • 后面的数值由前面的数值推导而得 ====》 从前往后遍历

   5. 举例推导dp数组

2. 代码

   class Solution {
       public int minCostClimbingStairs(int[] cost) {
           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];
   
       }
   }