代码随想录Day32 动态规划01 LeetCodeT509 斐波那契数列 T70 爬楼梯 T746 爬楼梯的最小消耗

前言:动态规划基础

动态规划首先可以解决的问题有背包问题,打家劫舍问题,股票问题,子序列问题等,主要是将一个大的问题切分成多个重叠的子问题,所以动态规划一定是上一个状态递推过来的,有一个重要的状态转移方程,但是这也并不是解题的全部,我们将动态规划的题目基本分为五步来完成,

1.搞明白dp数组的含义

2.搞明白状态转移方程怎么写

3.数组如何初始化

4.确定遍历方式

5.在错误的时候打印出dp数组查看分析问题

LeetCode T509 斐波那契数列

题目链接:509. 斐波那契数 - 力扣（LeetCode）

题目思路:

1.dp数组定义

这里我们定义一个数组来表示斐波那契数列

int[] dp = new int[n+1];

为什么要定义n+1个长度呢?你想想求dp[3]就知道了,前面有三个数字dp[0] = 0,dp[1] = 1      dp[2] = 1.

2.下面明白状态转移方程

我们都知道斐波那契数列式的第n项是由前两个加起来

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

3.初始化数组

初始化前两项,因为这两项要知道才能得到第三项

4.确定遍历方式

由于我们只需要得到第n项,直接for循环即可从前向后遍历

5.打印dp数组

题目代码:

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

注:这题也可以使用递归,是递归的经典例题,但是递归太慢了

LeetCode T70 爬楼梯

题目链接:70. 爬楼梯 - 力扣（LeetCode）

题目思路:

1.搞明白dp数组的含义

dp数组代表到到达第i个台阶有几种方法

2.搞明白状态转移方程怎么写

因为到达第i个台阶可能是两步上来的,也可能是一步上来的,那么我们到第i阶台阶就是第i-1个台阶的方法数加上i-2阶的方法数

这道题的推导公式是这样得来的：

在到达第n层的上一步，我们只有两个选择，走一步，或者走两步。

如果是走一步，我们需要先通过 f(n-1)种方式到达 n-1 层

如果是走两步， 我们需要通过 f(n-2)种方式到达第 n - 2 层

所以综上有 f(n) = f(n-2) + f(n-1)

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

3.数组如何初始化

初始化dp[0] = 1,dp[1] = 2

4.确定遍历方式

顺序遍历即可

5.在错误的时候打印出dp数组查看分析问题

题目代码:

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

LeetCode T746 爬楼梯的最小消耗

题目链接:746. 使用最小花费爬楼梯 - 力扣（LeetCode）

题目思路:

1.搞明白dp数组的含义

这里的dp数组表示的是爬楼梯到本层的最小消耗

2.搞明白状态转移方程怎么写

从前一层爬一层的消耗和前两层爬两层的消耗取最小值就是到达本层的最小消耗

3.数组如何初始化

由于题目说我可以选择在第层或者第一层出发,所以dp[0] = 0;dp[1] = 0

int[] dp = new int[cost.length+1];
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

4.确定遍历方式

从前往后顺序遍历即可,因为上层是围绕着下层结果而产生的

5.在错误的时候打印出dp数组查看分析问题

注:这里爬到的是cost数组后面那一层而不是cost数组的最后一个元素所在位置

题目代码:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length+1];
        if(cost.length == 0){
            return 0;
        }else if(cost.length == 1){
            return cost[0];
        }else{
            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];
    }
}