动态规划一

2020-05-25 19:57:27 # leetcode # 总结 # dynamic programming

动态规划（一）

一. 动态规划基础

1.1 什么是动态规划

我们首先需要知道我们为什么需要动态规划，动态规划的核心思想其实就是用空间换时间，而省时间的方式就是减少Brute Force或者递归中重复的子问题。

动态规划的基础是最优子结构，什么是最优子结构？其实就是从一个小规模问题推导出大规模问题的解。并且子问题之间不能相互影响，所以找出最优子结构，写出递推式是DP问题的最关键的部分，同时也是最难的部分。用花花酱的话来说，DP问题做多少都不嫌多。

最直接的例子就是斐波那契数列：

$$ f(n) = f(n - 1) + f(n - 2) $$

有可能要计算很多重复的子问题，如果使用一个数组记录已经计算过的f(n)，计算f(n + 1)时用到f(n)时可以直接返回，而不用再次递归。

1.2 动态规划思路

动态规划问题大多数都是求最值的，从比较小规模的最值，到当前规模的最值，一步步扩张。

1.2.1 top-down

递归 + memorization

自顶向下：其实就是普通的递归加上memorization，上面提到的斐波那契数列的例子就是top-down，简单来说就是从需要计算的解，从后向前推导，记录每一步的值，直到base case结束，也就是递归终点。

1.2.2 bottom-up

Loop + memorization

自底向上：从base case去递归求解下一个解，直到最终的目标解。以斐波那契额为例：

dp[1] = 1
dp[2] = 2
i = 3
while (i <= n) {
    dp[i] = dp[i - 1] + dp[i - 2];
    i++;
}

return dp[n];

1.2.3 注意事项

动态规划还需要注意的很重要的一点是边界，往往边界是递归返回的base case，或者用于padding。

1.3 动态规划分类

这里分类是向花花酱学习的分类方式，用数据规模，时间复杂度和空间复杂度进行分类。这里是花花酱整理的不同类型DP问题分类链接。

本次讨论的所有动态规划问题都是属于入门级难度，大部分是：“I: O(n), S = O(n), T = O(n)”，其中I表示的是输入量级，S表示空间复杂度，T表示时间复杂度。

注意，这里S的O(n)可能是O(2n),O(3n)，T也是如此，对于2n和3n的情况后面还会讨论，需要多做题熟悉。

二. 动态规划题目总结（2020.05.25）

本次的题目大都比较简单，比较简单的题目直接放链接和递推式，然后直接给出Java Code，需要额外写文章的这里给出链接。

2.1 LeetCode 53. Maximum Subarray

递推式：假设F(n)为从第1到n个数中包含当前数字的子序列的最大值。

$$ F(n) = max(F(n - 1) + num[n], num[n]) $$

class Solution {
    public int maxSubArray(int[] nums) {
        int resultMax = nums[0], currentMax = nums[0];

        for (int i = 1; i < nums.length; i++){
            currentMax = Math.max(currentMax + nums[i], nums[i]);
            resultMax = Math.max(resultMax, currentMax);
        }

        return resultMax;
    }
}

2.2 LeetCode 70. Climbing Stairs

递推式：假设F(n)为从第1到n级台阶的走法最大值。

$$ F(n) = F(n - 1) + F(n - 2) (F(1) = 1, F(2) = 2)$$

class Solution {
    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }

        int pre = 1, cur = 2;

        while (n-- > 2) {
            int temp = pre + cur;
            pre = cur;
            cur = temp;
        }

        return cur;
    }
}

2.3 LeetCode 121. Best Time to Buy and Sell Stock

递推式：假设F(n)为从第1到n天，买卖股票赚钱最多赚多少钱；tempMin(1, n)为从1到n的最最低价。

$$ F(n) = Math.max(F(n - 1), prices[n] - tempMin(1, n))$$

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2){
            return 0;
        }

        int result = prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0;
        int tempMin = prices[1] > prices[0] ? prices[0] : prices[1];

        for (int i = 2; i < prices.length; i++){
            result = prices[i] - tempMin > result ? prices[i] - tempMin : result;
            tempMin = prices[i] < tempMin ? prices[i] : tempMin;
        }

        return result;
    }
}

2.4 LeetCode 198. House Robber

递推式：假设F(n)为从第1家到第n家最多能获得的财富数目，nums[n]为第n家的财富。

$$ F(n) = Math.max(F(n - 1), F(n - 2) + nums[n]) (F(1) = nums[1], F(2) = Math.max(nums[1], nums[2])) $$

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int pre = nums[0], cur = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            int temp = cur;
            cur = Math.max(pre + nums[i], cur);
            pre = temp;
        }

        return cur;
    }
}

2.5 LeetCode 303. Range Sum Query - Immutable

这道题我不觉得算是一道DP题目，最多算caching，硬要说的话也的确有dp减少重复子问题的思想在。

class NumArray {

    int[] sums;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            sums = new int[nums.length];
            sums[0] = nums[0];

            for (int i = 1; i < nums.length; i++) {
                sums[i] = nums[i] + sums[i - 1];
            }
        }
    }

    public int sumRange(int i, int j) {
        return i - 1 < 0 ? sums[j] : sums[j] - sums[i - 1];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

2.6 LeetCode 746. Min Cost Climbing Stairs

注意：这道题里，登上最终台阶的意思不是数组的最后一级，而是数组的最后一级再向后数一级，也就是说要越过它，到达n+1起始位置我们可以理解为从0级台阶开始，cost为0。

递推式：假设F(n)为从第1级到跨越n级所需要的最小cost(从n-1跳就不需要加上cost[n]，从n-2跳就需要)。

$$ F(n) = Math.min(F(n - 1), F(n - 2) + cost[n - 1]) (F(1) = nums[0], F(2) = Math.min(nums[0], nums[1]))$$

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        int n = cost.length;
        Arrays.fill(dp, 0);
        dp[0] = cost[0];
        dp[1] = cost[1];

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

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

2.7 LeetCode 1137. N-th Tribonacci Number

递推式：已经很明显地告知递推式了，且0 <= n <= 37无需多言。

$$ F(n) = F(n - 1) + F(n - 2) + F(n - 3) (n >= 3, F(1) = 0, F(1) = 1, F(2) = 1)$$

class Solution {
    int[] res = new int[38];
    public int tribonacci(int n) {
        res[0] = 0;
        res[1] = 1;
        res[2] = 1;

        if (n < 3 || res[n] > 0) {
            return res[n];
        }

        res[n] = tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);

        return res[n];
    }
}

2020-05-25 19:57:27 # leetcode # 总结 # dynamic programming