经典算法——动态规划

2022-05-05  本文已影响0人  _冻茶

姓名：谭旭东 学号：19011210016

前言

  1. 动态规划是什么？
  1. 如何学习动态规划？

一、简单相加的状态转移

这类动态规划属于比较简单的情况，因为转移方程可以简单的直接得到

而且由于新状态转移只需要前几个状态，我们可以压缩状态来节省更多空间

1. 斐波那契数列

不使用状态压缩：

    public int fib(int n) {
        if (n == 0) return 0;
        if ( n == 1 || n == 2) return 1;

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

        for (int i = 2; i<=n; i++) {
            dp[i] = f0 + f1;
        }
        return dp[n];
    }

状态压缩后：

    public int fib(int n) {
        if (n == 0) return 0;
        if ( n == 1 || n == 2) return 1;

        int f0 = 0;
        int f1 = 1;

        for (int i = 1; i<n; i++) {
            int newf = f0 + f1;

            f0 = f1;
            f1 = newf;
        }
        return f1;
    }

2. 第 N 个泰波那契数

直接上状态压缩之后的代码

    public int tribonacci(int n) {
        if ( n == 0 ) return 0;
        if ( n  <= 2) return 1;

        int t0 = 0;
        int t1 = 1;
        int t2 = 1;

        for (int i = 3; i <= n; i++) {
            
            int newT = t0 + t1 + t2;

            t0 = t1;
            t1 = t2;
            t2 = newT;
        }
        return t2;
    }

3. 爬楼梯

状态压缩后的代码：

    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2; 


        int dp1 = 1;
        int dp2 = 2;

        for (int i = 3; i <= n; i++) {
            int newDp = dp1 + dp2;
            dp1 = dp2;
            dp2 = newDp;
        }

        return dp2;
    }

二、取max/min的状态转移

这种状态转移方程需要在转移过程中选取最小/最大值

1. 最小花费爬楼梯

只需要前两个状态，所以还是可以状态压缩（注释掉的是没进行状态压缩的版本）

    public int minCostClimbingStairs(int[] cost) {

        int len = cost.length;

        if (len == 1) return 0;
        if (len == 2) return Math.min(cost[0],cost[1]);


        // int[] dp = new int[len + 1];

        int dp1 = 0;
        int dp2 = 0;

        for (int i = 2; i<=len; i++) {
            // dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
            int newdp = Math.min(dp1+cost[i-2],dp2+cost[i-1]);

            dp1 = dp2;
            dp2 = newdp;

        }
        // return dp[len];
        return dp2;
    }

2. 打家劫舍

代码如下，状态压缩版本（注释掉的是非状态压缩版）

    public int rob(int[] nums) {
        
        int len = nums.length;

        if (len == 1) return nums[0];
        if (len == 2) return Math.max(nums[0],nums[1]);


        // int[] dp = new int[len];
        // dp[0] = nums[0];
        // dp[1] = Math.max(nums[0],nums[1]);

        int dp0 = nums[0];
        int dp1 = Math.max(nums[0],nums[1]);

        for (int i = 2; i < len; i++) {
            // dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i]);
            int newDp = Math.max(dp1 , dp0 + nums[i]);

            dp0 = dp1;
            dp1 = newDp;
        }

        // return dp[len-1];
        return dp1;

    }

3. 打家劫舍2

不同点在于：这里的房屋（数组）是首尾相连的，也就是说打劫了第一家，就不能打劫最后一家；打劫了最后一家，就不能打劫第一家

根据这种情况，我们将数组分为nums[0,len-1]和nums[1,len]，然后分别通过上一题的方式进行求解，然后返回两个解的最大值即可

代码如下

    public int rob(int[] nums) {
        
        int n = nums.length;

        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0],nums[1]);


        int[] nums1 = Arrays.copyOfRange(nums , 0 , n - 1);
        int[] nums2 = Arrays.copyOfRange(nums , 1 , n);

        int ans1 = findMax(nums1);
        int ans2 = findMax(nums2);

        return Math.max(ans1 , ans2);
    }

    public int findMax(int[] nums) {

        int n = nums.length;

        if (n == 2) return Math.max(nums[0] , nums[1]);



        int dp0 = nums[0];
        int dp1 = Math.max(nums[0],nums[1]);

        for (int i = 2 ; i < n; i++) {
            int newdp = Math.max(dp1,dp0 + nums[i]);

            dp0 = dp1;
            dp1 = newdp;
        }

        return dp1;
    }

4. 删除并获得点数

代码如下：

    public int deleteAndEarn(int[] nums) {

        int max = 0;

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

        if (max == 1) return nums.length;

        int[] count = new int[max + 1];
        int[] dp = new int[max + 1];

        for (int i = 0; i < nums.length; i++) {
            ++count[nums[i]];
        }

        dp[1] = count[1];
        dp[2] = Math.max(count[1], count[2] * 2);

        for (int i = 3; i <= max; i++) {
            dp[i] = Math.max(dp[i - 2] + count[i] * i, dp[i - 1]);
        }

        return dp[max];
    }

三、嵌套的状态转移

这种DP的状态转移，会和之前的所有状态有关，不可进行状态压缩

1. 跳跃游戏2

动态规划版本的代码如下：


    public int jump(int[] nums) {

        int len = nums.length;

        if (len == 1) return 0;


        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 1; i < len; i++) {

            for (int j = 0; j < i; j++) {

                if (j + nums[j] >= i)
                    dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }

        return dp[len - 1];
    }

其实该题目还能用BFS去做，不断对节点松弛，有点类似于SPFA算法，代码如下：

    public int jump(int[] nums) {
        int len = nums.length;
        int[] d = new int[len];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[len - 1] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(len - 1);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < len; i++) {
                if (nums[i] >= cur - i) {       // 判断能否到达
                    if (d[cur] + 1 < d[i]) {    // 是否松弛成功，成功才入队
                        d[i] = d[cur] + 1;
                        queue.add(i);
                    }
                }
            }
        }
        return d[0];
    }

四、连续子数组状态转移

这类题目往往要求连续子数组的最大/最小和值，我们在遍历数组时通过一个sum（子数组和）值不断更新最大/最小值，最后可以得到结果

1. 最大子序和

要用语言表达思路，实在是...
还是直接上代码把，要去品...

    public int maxSubArray(int[] nums) {

        int ans = Integer.MIN_VALUE;
        int sum = 0;

        for(int i=0; i< nums.length; i++) {
            if (sum <= 0) {
                sum = nums[i];
            } else {
                sum += nums[i];
            }

            ans = Math.max(ans , sum);
        }
        return ans;
    }

2. 环形子数组的最大和

思路：其实和上题基本一致，但是由于这里是首尾相连，我们需要分情况讨论

代码：注意，求第二种情况需要去掉首尾元素！

    public int maxSubarraySumCircular(int[] nums) {

        if (nums.length == 1) return nums[0];

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int sum1 = 0;
        int sum2 = 0;

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            sum += nums[i];

            if (sum1 <= 0)
                sum1 = nums[i];
            else
                sum1 += nums[i];

            max = Math.max(max, sum1);
        }


        for (int i = 1; i < nums.length - 1; i++) {

            if (sum2 >= 0)
                sum2 = nums[i];
            else
                sum2 += nums[i];

            min = Math.min(min, sum2);
        }

        return Math.max(sum - min, max);
    }

3. 乘积最大的子数组

    public int maxProduct(int[] nums) {

        int max = nums[0];

        // 前置最大最小乘积
        int preMax = nums[0];
        int preMin = nums[0];

        int len = nums.length;

        for (int i = 1; i < len; i++) {


            /**
             * 当前的最大最小值
             * 可能由前置的最大最小值乘以正数/负数得到
             */
            int curMax = Math.max(preMax * nums[i], preMin * nums[i]);
            int curMin = Math.min(preMax * nums[i], preMin * nums[i]);

            /**
             * 是0的情况，会从nums[i+1]重新开始
             * 所以我们需要加入以下语句，以免curMax和curMin都为0
             * 之后乘积就全部为0了
             */
            preMax = Math.max(nums[i], curMax);
            preMin = Math.min(nums[i], curMin);

            max = Math.max(preMax, max);
        }
        return max;
    }

4. 乘积为正数的最长子数组

    public int getMaxLen(int[] nums) {

        int len = nums.length;

        int[] pos = new int[len];
        int[] neg = new int[len];

        // 初始化
        if (nums[0] > 0) pos[0] = 1;
        else if (nums[0] < 0) neg[0] = 1;

        int max = pos[0];

        for (int i = 1; i < len; i++) {
            if (nums[i] > 0) {
                pos[i] = pos[i - 1] + 1;
                neg[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
            } else if (nums[i] < 0) {
                pos[i] = neg[i - 1] == 0 ? 0 : neg[i - 1] + 1;
                neg[i] = pos[i - 1] + 1;
            } else {
                pos[i] = 0;
                neg[i] = 0;
            }
            max = Math.max(max, pos[i]);
        }

        return max;
    }

5. 最佳观光组合

其实这题的总体思路就是在遍历过程中维护一个最大值
代码如下：

    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0;
        int maxVi = values[0] + 0;

        for (int j = 1; j < values.length; j++) {
            ans = Math.max(ans , maxVi + values[j] - j);

            if (values[j] + j > maxVi)
                maxVi = (values[j] + j);
        }
        return ans;
    }

五、 买卖股票问题

这类题目模拟股票的买入和卖出，其实就是要我们对股票的状态进行一个模拟，实现完整的过程并且将所有结果模拟出来进行对比

1. 买卖股票的最佳时机

代码：

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i<len; i++) {
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1] , -prices[i]);
        }

        return dp[len - 1][0];
    }

2. 买卖股票的最佳时机2

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i<len; i++) {
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i]);
        }

        return dp[len - 1][0];
    }

3. 最佳买卖股票时机含冷冻期

    public int maxProfit(int[] prices) {

        int len = prices.length;

        int[][] dp = new int[len][3];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }

        return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));
    }

4. 买卖股票的最佳时机含手续费

    public int maxProfit4(int[] prices, int fee) {

        int len = prices.length;

        int[][] dp = new int[len][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }

六、0-1背包问题

基本概念：

1. 分割等和子集

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;

        for (int i = 0; i < len; i++) sum += nums[i];

        if (sum % 2 == 1) return false;     // 奇数无法二分

        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
    
    
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                if (i - num >= 0) {
                    dp[i] = dp[i] || dp[i - num];
                }
            }
        }
        return dp[target];
    }

2. 目标和

    public int findTargetSumWays(int[] nums, int target) {

        int len = nums.length;

        int sum = 0;
        for (int i = 0; i < len; i++) sum += nums[i];

        if (target > sum || target < -sum || (target + sum) % 2 == 1) return 0;
        int x = (sum + target) / 2;

        int[] dp = new int[x + 1];
        dp[0] = 1;                      // 目标和为0，可以不选，故总共有一种方案

        for (int num : nums) {
            for (int i = x; i >= num; --i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[x];
    }


    public int findTargetSumWays2(int[] nums, int target) {
        int len = nums.length;

        int sum = 0;

        for (int i = 0; i < len; i++) sum += nums[i];

        if (target > sum || target < -sum) return 0;

        // i表示使用了前几个数组num
        // j表示能够构成的结果，范围为-sum到sum，下面使用时需要加入偏移量
        int[][] dp = new int[len + 1][sum * 2 + 1];
        dp[0][sum] = 1;     // 使用0个元素构成0，方案有一种

        for (int i = 1; i <= len; i++) {
            int num = nums[i - 1];
            for (int j = -sum; j <= sum; j++) {
                if (j + sum - num >= 0)
                    dp[i][j + sum] += dp[i - 1][j + sum - num];
                if (j + sum + num <= 2 * sum)
                    dp[i][j + sum] += dp[i - 1][j + sum + num];
            }
        }

        // 所有数都用上，能构成target的方案数量
        return dp[len][target + sum];
    }

七、完全背包问题

基本概念：

1. 单词拆分

    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();

        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for (int i = 1; i <= len; i++) {
            for (String curS : wordDict) {
                int size = curS.length();

                if (i - size >= 0 && s.substring(i - size, i).equals(curS))
                    dp[i] = dp[i] || dp[i - size];
            }
        }
        return dp[len];
    }

2. 完全平方数

    public int numSquares(int n) {

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int num = 1; num <= Math.sqrt(n); num++) {
            int squareNum = num * num;
            for (int i = 0; i <= n; i++) {
                if (i - squareNum >= 0)
                    dp[i] = Math.min(dp[i], dp[i - squareNum] + 1);
            }
        }
        return dp[n];
    }

3. 组合总和

4. 零钱兑换

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 100000);        // 如果填充MAX_VALUE，可能需要考虑反转问题，所以随便找一个大数填入
        dp[0] = 0;      // 没有面额为0的硬币

        for (int i = 1; i <= amount; i++) {

            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == 100000 ? -1 : dp[amount];
    }

5. 零钱兑换2

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = 1; i <= amount; i++) {
                if (i - coin >= 0)
                    dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

``

···java

上一篇 下一篇

猜你喜欢

热点阅读