一、动态规划简介
动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
1.1 三个基本概念
- 最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。
- 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
- 重复子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
1.2 动态规划组成部分
- 确定状态
- 研究最优策略的最后一步
- 化为子问题
- 转移方程
- 根据子问题定义直接得到f(1), f(2), … f(n - 1)与f(n)的关系
- 初始条件和边界情况
- 细心,考虑周全
- 计算顺序
- 利用之前的计算结果
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;
}
}