代码随想录训练营第三十八天 ｜ 动态规划

今天是第三十八天，最难的动态规划要开始了

509. 斐波那契数 

class Solution {
    public int fib(int n) {
        if(n < 2){
            return n;
        }int[] fibNum = new int[n+1];

        fibNum[0] = 0;
        fibNum[1] = 1;

        for(int i = 2; i<= n; i++){
            fibNum[i] = fibNum[i-1]+fibNum[i-2];

        }
        return fibNum[n];
    }
}

最基础的dp，用前面数组的值来组成当前数组的值

70. 爬楼梯 

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

和上一题一个思路，这一步可以通过step[n-1]迈一步和step[n-2]迈两步来实现，因此把它们两个加起来就是当前这一步的拥有的可能性。

746. 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        for(int i = 2; i<n;i++){
            cost[i] = Math.min(cost[i-1] + cost[i], cost[i-2]+cost[i]);

        }
        return Math.min(cost[n-1], cost[n-2]);
    }
}

通过让当前步数加上之前的代价来判断达到当前步数的代价大小。直接返回可以到达当前步数的最小代价即可。

今天都是最基础的dp，但是难点就要来了。