LeetCode算法训练-动态规划

欢迎关注个人公众号：爱喝可可牛奶

LeetCode算法训练-动态规划

理论知识

动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移

动态规划需要借助dp数组，可能是一维也可能是二维的

1. 首先要明确dp数组是用来干什么的，下标对应什么
2. 状态如何转移 ？ 也就是理清递推公式
3. dp数组如何初始化
4. 如何遍历
5. 举个栗子模拟推导一遍

LeetCode 509. 斐波那契数

分析

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

代码

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 index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}

LeetCode 70. 爬楼梯

分析

错误 没有理清递推函数

class Solution {
    public int climbStairs(int 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]+2;
        }
        return dp[n];
    }
}

dp[i]表示到当前楼梯有多少种跳法，从这里可以往后跳一步或者两步，这样就建立了前后阶梯的关系，但是不能跳2个一步

当前阶梯跳数能由前一个阶梯跳一步或前两个阶梯跳两步得到

代码

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

LeetCode 746. 使用最小花费爬楼梯

整数数组 cost ，cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

分析

根据测试用例能够得出台阶顶部在哪里，cost[i] ：从下标i-1爬一步，从i-2爬两步到台阶顶部

dp[i]表示爬到第i个台阶的最小花费，

状态转移：dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

代码

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];
    }
}

总结

1. 搞清楚dp数组含义以及对应下标反映了什么状态
2. 弄清楚转移公式
3. 初始化
4. 确定遍历顺序（这个和转移公式紧密相关）
5. 模拟一下