LeetCode刷题之动态规划算法

动态规划（英语：Dynamic programming，简称 DP）

是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。斐波那契数列 0,1,1,2,3,5,8,13,…有着一个相当简单的描述方式，它的每个数字都与前两个紧邻的数字相关。如果 F(n) 是第 n 个数字，那么我们会有 F(n) = F(n-1) + F(n-2)。这个在数学上称作递归方程或者递推关系。为了计算后面的项，它需要前面项的计算结果作为输入。

解决方案

自上而下：

你从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储（Memoization）。

自下而上：

你可以直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法（Tabulation，table-filling algorithm**）。
至于迭代和递归与这两种方法的关系，自下而上用到了迭代技术，而自上而下则用到了递归技术。

动态规划、分治法、贪心算法异同点

相同点：

动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

不同点：

• 分治法

分治法中的各个子问题是独立的，利用子问题的解，合并成该问题的解。

• 贪心算法

只有同一个问题，依赖于当前已经做出的所有选择。
自顶向下处理，每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。

• 动态规划

动态规划中的各个子问题是不独立的，动态规划任何一个i+1阶段都仅仅依赖 i 阶段的处理，而与i之前的选择无关。

自底向上处理，每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题，得到整个问题最优解。

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

题解：

class Solution {
    public int maxProfit(int[] prices) {
        //思路：从最后一天往前遍历，看最后一天卖出能得到的最大利润，依次往前得出每天卖出的最大利润，取出最大值为最大利润，如果最大值还为负数，则
        //最大利润为0，不进行交易
        int maxProfit = 0;
        for (int i=prices.length-1;i>=1;i--) {  //从第二天到最后一天都可能是卖出的天数，但第一天不能卖，因为还没买

            for (int j=i-1;j>=0;j--) { //从卖出的前一天到第一天为可能买的日期，得出利润
                if (prices[i]-prices[j] > maxProfit) {
                    //利润有更大的需要更新
                    maxProfit = prices[i]-prices[j];
                }
            }
        }
        return maxProfit;
    }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2

解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

题解1：

class Solution {

    public int climbStairs(int n) {
                    //思路：用动态规划思想，要爬到n阶，可以通过最后爬一步和两步2中爬法到，到n阶的方法等于到n-1阶方法加上n-2阶方法，即f(n)=f(n-1)+f(n-2)，这个f(n)方法就用递归实现
        //此外，f(n)=f(n-1)+f(n-2)，从n为3开始，该函数计算得出的是一个斐波那契数列，当前数为前两个数之和，所以有两种解法
        if (n < 3) {
            return n;
        }

        int a = 1;
        int b = 2;
        int cur = 0;
        for (int i=3;i<=n;i++) {
            cur = a + b;
            a = b;
            b = cur;
        }
        return cur;
    }

}

题解2：

class Solution {
     public int climbStairs(int n) {
        //思路：用动态规划思想，要爬到n阶，可以通过最后爬一步和两步2中爬法到，到n阶的方法等于到n-1阶方法加上n-2阶方法，即f(n)=f(n-1)+f(n-2)，这个f(n)方法就用递归实现
        
        return getStepWay(n);
    }

    /**
     * 计算n级台阶不同走法
     * @param n
     * @return
     */
    public int getStepWay(int n) {
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        return getStepWay(n-1) + getStepWay(n-2);
    }
}

1025. 除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

示例 1：

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：

输入：3
输出：false

解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

题解：

class Solution {
       /**
     * 思路：
     * 动态规划，先从dp[1],dp[2]
     * dp[n] 表示N=n时的结果，dp[n]类型为boolean类型 true为爱丽丝赢
     * 那么dp[1]=false,dp[2]=true
     * 然后往后推，如果i中有约数j，dp[i-j]=false，那么dp[i]=true
     * 如果i中，所有dp[i-j]没有为false情况，那么dp[i]=false;
     * 
     * 我们用DP来求解这个问题，首先new一个长度为N+1的数组，dp[i]表示i这个数是否可以赢，如果为true则N=i可以赢，为false则输。
     * N=1，爱丽丝就肯定会输，所以我们首先让dp[1]=false;
     * 然后我们从i=2开始，一直遍历到i=N
     * 按照题意，我们让j每次从1到i-1的区间里取数，且需要满足
     * 选出任一 x，满足 0 < x < N 且 N % x == 0 。
     * 这个条件，如果发现dp[j]=false，那么dp[i]就一定会赢。
     */
    public boolean divisorGame(int N) {
        boolean[] dp = new boolean[N+1];

        if (N == 1) {
            return false;
        }

        dp[1] = false;
        dp[2] = true;

        for (int i=3;i<=N;i++) {
            //i表示某次开始选择的数，用j表示下一次选的数，j为i的约数，所以j的范围为1到i/2
            dp[i] = false;
            for (int j=1;j<=i/2;j++) {
                if (i%j==0 && dp[i-j]==false) {
                    //下一次人选的为false，那么该人就胜了，为ture
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }

        /**
     * 思路： 归纳法
     * 如果数是奇数，因为只用1与本身才能让余数为0，所以必然会让接下来的数变为偶数
     * 首先要明确的是，到谁是数为2，那么就是谁赢，所以如果刚开始数是偶数，那么每次就让爱丽丝选1，这样每次在奇数是就让鲍勃来选，再让数变为偶数，最后一定是到爱丽丝选时，数为2
     * 同理，如果数为奇数，那么到鲍勃时数为偶数，鲍勃也这么做就能取得胜利，所以最后判断胜利条件，就是数的奇偶性
     * @param N
     * @return
     */
    public boolean divisorGame(int N) {
        return N%2==0;
    }
}

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

题解：

class Solution {
    /**
     * 思路：
     * 状态定义： 设动态规划列表dp ，dp[i]代表以元素nums[i]为结尾的连续子数组最大和。
     *
     * ​我们发现dp[i]就是以数组下标为i的数做为结尾的最大子序列和，
     * 注意是以i为结尾，比如说现在有一个数组{6,-3,-2,7,-15,1,2,2}，为了不搞，我们就下标以1开始，dp[3]就是以-2为结尾的，
     * 那么显然dp[3]的最大值就是1咯（6，-3，-2），dp[4]要以7结尾那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
     *
     * ​ 知道dp[i]是啥后，现在我们开始细细品一下上面这个递推式，求dp[i]的时候是不是有两种可能，
     * 要么就是像上面的dp[4]一样，dp[3]求出来是1了，再加上自己array[4]是最大的，那么还有一种可能就是说如果dp[3]我求出来是-100，
     * 那如果我也是dp[3]+array[4]的话是-93，这时候dp[3]反而是累赘，最大就是自己（因为前面定义了必须以i为结尾，也就说必须以7结尾）。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i=1;i<nums.length;i++) {
            //如果i前一个数的子数组和小于0，就不要加上前面的累赘了，否则就加上
            dp[i] = nums[i] + Math.max(dp[i-1], 0);

            //遍历的同时获取dp数组中的最大值
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}