一、动态规划简介

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

1.1 三个基本概念

  • 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。
  • 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
  • 重复子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

1.2 动态规划组成部分

  1. 确定状态
    • 研究最优策略的最后一步
    • 化为子问题
  2. 转移方程
    • 根据子问题定义直接得到f(1), f(2), … f(n - 1)与f(n)的关系
  3. 初始条件和边界情况
    • 细心，考虑周全
  4. 计算顺序
    • 利用之前的计算结果

1.3 与其他算法的关系

分治 动态规划 贪心
适用类型 通用 优化 优化
子问题 每个都不同 有很多重复 只有一个
最优子结构 没有要求 必须满足 必须满足
子问题数 全部都要解 全部都要解 只解一个

二、线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

2.1 单串问题

最经典单串LIS问题

最长递增子序列⭐

⚡ 动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;

        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

⚡ 贪心 & 二分⭐

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // id[i] 表示长度为i的递增子序列末尾最小值
        int[] id = new int[n + 1];
        int tt = 0;

        id[tt] = 0;
        for (int i = 0; i < n; ++i) {
            int l = 0, r = tt;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (id[mid] < nums[i]) l = mid;
                else  r = mid - 1;
            }
            id[r + 1] = nums[i];
            tt = Math.max(tt, r + 1);
        }
        return tt;
    }
}

最长递增子序列的个数

⚡ 动态规划

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] lengths = new int[n];//存以i号位置元素结尾的最长子序列
        int[] counts = new int[n];//以i位置元素结尾的最长子序列的数量

        for (int i = 0; i < n; ++i) {
            lengths[i] = 1; counts[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                   if (lengths[j] >= lengths[i]) {
                       lengths[i] = lengths[j] + 1;
                       counts[i] = counts[j];
                   }
                   else if (lengths[j] + 1 == lengths[i]) {
                       counts[i] += counts[j];
                   }
                }
            }
        }
        int longest = 0, count = 0;
        for (int len : lengths) {
            longest = Math.max(longest, len);
        }
        for (int i = 0; i < n; ++i) {
            if (lengths[i] == longest) {
                count += counts[i];
            }
        }
        return count;
    }
}

俄罗斯套娃信封问题🌟

⚡ 动态规划

class Solution {
    public int maxEnvelopes(int[][] envelopes) {

        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                else return o2[1] - o1[1];
            }
        });

        int n = envelopes.length;
        //dp[i]表示以i号信封结尾的组合中最大信封个数
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

最大子数组和系列

最大子序和⭐（Kanade算法）

⚡ 动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            //dp[i]表示包括以i号数字结尾的字符串的最大值
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

⚡ 优化掉dp数组

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int lastNum = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            lastNum = Math.max(lastNum + nums[i], nums[i]);
            ans = Math.max(lastNum, ans);
        }
        return ans;
    }
}

乘积最大子数组

⚡ 动态规划

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        //考虑正负数相乘，维护一个最大和一个最小的dp数组
        int[] maxDp = new int[n];
        int[] minDp = new int[n];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; ++i) {
            maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(minDp[i - 1] * nums[i], nums[i]));
            minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(maxDp[i - 1] * nums[i], nums[i]));
            ans = Math.max(ans, maxDp[i]);
        }
        return ans;
    }
}

⚡ 优化掉dp数组

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxP = nums[0];
        int minP = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; ++i) {
            int mx = maxP, mn = minP;
            maxP = Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i]));
            minP = Math.min(mn * nums[i], Math.min(mx * nums[i], nums[i]));
            ans = Math.max(ans, maxP);
        }
        return ans;
    }
}

环形子数组的最大和⭐

⚡ 动态规划
若使用到了环，则最大子序列中必定包含A[n-1]和A[0]两个元素，且说明从A[1]到A[n-2]这个子数组中必定包含负数，否则只通过一趟最大子序和就可以得出结果。
因此只需要把A[1]-A[n-2]间这些负数的最小和求出来，用整个数组的和 sum减掉这个负数最小和即可实现原环型数组的最大和。最后再与无环子序列情况下得到最大和进行比较即可。

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int n = A.length;
        if (n == 1) return A[0];

        int[] dp = new int[n];
        dp[0] = A[0];
        int ansMax = dp[0]; //不使用环的情况下子数组的最大和
        int sum = A[0];

        for (int i = 1; i < n; ++i) {
            dp[i] = Math.max(dp[i - 1] + A[i], A[i]);
            ansMax = Math.max(ansMax, dp[i]);
            sum += A[i];
        }

        dp[1] = A[1];
        int ansMin = dp[1]; //使用环的情况下1到n-2内子数组的最小和
        for (int i = 2; i < n - 1; ++i) {
            dp[i] = Math.min(dp[i - 1] + A[i], A[i]);
            ansMin = Math.min(ansMin, dp[i]);
        }
        //sum - ansMin即为使用环的情况下的子数组最大和
        return Math.max(ansMax, (sum - ansMin));
    }
}

打家劫舍系列

打家劫舍

⚡ 动态规划

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

打家劫舍 II

见LeetCode每日打卡-April4月15日

股票系列

买卖股票的最佳时机

⚡ 单次遍历

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            ans = Math.max(ans, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return ans;
    }
}

买卖股票的最佳时机II

⚡ 动态规划

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; ++i) {
            //转移方程
            dp[i] = dp[i - 1] + Math.max(prices[i] - prices[i - 1], 0);
        }
        return dp[n - 1];
    }
}

⚡ 贪心

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

其他问题

丑数II

见LeetCode每日打卡-April4月11日

直方图的水量⭐

见LeetCode每日打卡-April4月2日

跳跃游戏

⚡ 动态规划 Time: O(n2) Space: O(n)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; ++i) {
            dp[i] = false;
            for (int j = 0; j < i; ++j) {
                if(dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }
}

⚡ 贪心 Time: O(n) Space: O(1)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxlen = 0;
        for (int i = 0; i < n; ++i) {
            if (maxlen >= i) {
                maxlen = Math.max(maxlen, nums[i] + i);
                if (maxlen >= n - 1) return true;
            }
        }
        return false;
    }
}

2.2 双串问题

最经典的双串LCS系列

最长公共子序列

⚡ 经典问题

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int dp[][] = new int[m+1][n+1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                //转移方程
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
}

带维度的双串问题

扰乱字符串🌟

见LeetCode每日打卡-April4月16日

2.3 矩阵问题

三角形最小路径和

⚡ 动态规划

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int[][] dp = new int[m][m];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < m; ++i) {
            dp[i][0] = triangle.get(i).get(0) + dp[i - 1][0];
            for (int j = 1; j < i; ++j) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
            }
            dp[i][i] = triangle.get(i).get(i) + dp[i - 1][i - 1];
        }

        int ans = dp[m - 1][0];
        for (int num : dp[m - 1]) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}
Pages: 1 2
赏

Try and fail, but don't fail to try.