第九章 动态规划part01

理论基础

• 文章
• 视频

cr：代码随想录

• 动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
• 需要注意
  • dp数组及下标的含义
  • 递推公式
  • dp数组如何初始化
  • 遍历顺序
  • 打印数组

509. 斐波那契数

很简单的动规入门题，但简单题使用来掌握方法论的，还是要有动规五部曲来分析。
文章讲解

思路
DP五部曲

1. 确定dp数组以及下标的含义
   dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式
   题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3. dp数组如何初始化
   题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
dp[1] = 1;

4. 确定遍历顺序
   从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推导dp数组
   按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
   0 1 1 2 3 5 8 13 21 34 55
   如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

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

    }
}

70. 爬楼梯

本题大家先自己想一想， 之后会发现，和 斐波那契数 有点关系。
文章讲解

class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return n;// 因为下面直接对dp[2]操作了，防止空指针
        /**
        * 1. 确定dp数组以及下标的含义
        * dp[i]： 爬到第i层楼梯，有dp[i]种方法
        */ 
        int[] dp = new int[n + 1]; //由于我们需要计算并存储从第0个台阶到第 n 个台阶的方法数，因此需要 dp[0] 到 dp[n]，共 n + 1 个元素。
        /** 
        * 2. 确定递推公式
        * 对于第 i 个台阶，有两种方式到达：
        * 从 i-1 台阶走1步。
        * 从 i-2 台阶走2步。
        * 因此，dp[i] = dp[i - 1] + dp[i - 2]
        */ 
        
        // 3. dp数组如何初始化
        dp[1] = 1;
        dp[2] = 2;

        // 4. 确定遍历顺序：从后向前
        // 5. 举例推导dp数组
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

这道题目力扣改了题目描述了，现在的题目描述清晰很多，相当于明确说 第一步是不用花费的。
更改题目描述之后，相当于是 文章中 「拓展」的解法
文章讲解

思路

1. 确定dp数组以及下标的含义
   dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
2. 确定递推公式
   可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
   dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
   dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
   那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？
   一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. dp数组如何初始化
   新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。
   所以初始化 dp[0] = 0，dp[1] = 0;
4. 确定遍历顺序：从前向后
5. 举例推导dp数组

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= len; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[len];
    }
}