动态规划(Dynamic Programming), 简称DP, 是求解最优化问题的一种常用策略
通常的求解思路为
- 暴力递归, 自顶下下, 但是会出现重复计算的问题
- 记忆化搜索, 自顶下下
- 递推, 自底向上
常规步骤如下
- 定义状态, 状态时原问题, 子问题的解, 比如dp(i) 的含义
- 设置初始状态, 边界, 比如设置dp(0) 的值
- 确定状态转移的方程, 比如确定dp(i) 和dp(i - 1) 的关系
其中的状态, 可以理解为, 会变化的状态
能用动态规划来解决的问题, 通常具备2 个特点
- 最优子结构, 最优化原理, 通过求解子问题的最优解, 可以获得原问题的最优解
- 无后效性
- 某个阶段状态一旦确定, 则此后过程的变化不再受此前各状态及决策的影响
- 在推导后面阶段的状态时, 只关心前面阶段的具体状态值, 不关系这个状态是怎么推导出来的
例1, 找零钱问题
假设有25, 20, 5, 1 分的零钱, 找给客户41 分的零钱, 如何办到硬币个数最少
用贪心策略得到的为5 枚硬币, 但并非最优解
假设dp(n) 是凑到n 分需要的最少硬币个数
- 如果第1 次选择了25 分的硬币, 那么dp(n) = dp(n - 25) + 1
- 如果第2 次选择了20 分的硬币, 那么dp(n) = dp(n - 20) + 1
- 如果第3 次选择了5 分的硬币, 那么dp(n) = dp(n - 5) + 1
- 如果第4 次选择了1 分的硬币, 那么dp(n) = dp(n - 1) + 1
所以dp(n) = min{dp(n - 25), dp(n - 20), dp(n - 5), dp(n - 21)} + 1
类似斐波那契数列的递归, 会有大量的重复计算, 复杂度较高
// 暴力递归, 重叠子问题
static int coins1(int n) {
if (n < 1) return Integer.MAX_VALUE;
if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
int min1 = Math.min(coins1(n - 25), coins1(n - 20));
int min2 = Math.min(coins1(n - 5),coins1(n - 1));
return Math.min(min1, min2) + 1;
}
优化- 记忆化搜索
使用数组, 将之前计算过的值存储, 如果计算下一个值时, 之前存过, 直接取出赋值即可
/**
* 记忆化, 自顶向下调用
* @param n
* @return
*/
static int coins2(int n) {
if (n < 1)return -1;
int[] dp = new int[n +1];
// dp[1] = dp[5] = dp[20] = dp[25] = 1;
int[] faces = {1, 5, 20 , 25};
for (int face : faces) {
if (n < face) break;
dp[face] = 1;
}
return coins2(n, dp);
}
static int coins2(int n, int[] dp) {
if (n < 1) return Integer.MAX_VALUE;
if (dp[n] == 0) {
int min1 = Math.min(coins2(n - 25, dp), coins2(n - 20, dp));
int min2 = Math.min(coins2(n - 5, dp),coins2(n - 1, dp));
dp[n] = Math.min(min1, min2) + 1;
}
return dp[n];
}
优化- 递推
自底向上计算, 存储到dp(i) 中, 逐步计算得出最后的结果
/**
* 递推, 自底向上
* @param n
* @return
*/
static int coins3(int n) {
if (n < 1) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
if (i >= 1) min = Math.min(dp[i - 1], min);
if (i >= 5) min = Math.min(dp[i - 5], min);
if (i >= 20) min = Math.min(dp[i - 20], min);
if (i >= 25) min = Math.min(dp[i - 25], min);
dp[i] = min + 1;
}
return dp[n];
}
优化- 记录选择的哪些硬币
static int coins4(int n) {
if (n < 1) return -1;
int[] dp = new int[n + 1];
int[] faces = new int[dp.length];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
if (i >= 1 && dp[i - 1] < min) {
min = dp[i - 1];
faces[i] = 1;
}
if (i >= 5 && dp[i - 5] < min) {
min = dp[i - 5];
faces[i] = 5;
}
if (i >= 20 && dp[i - 20] < min) {
min = dp[i - 20];
faces[i] = 20;
}
if (i >= 25 && dp[i - 25] < min) {
min = dp[i - 25];
faces[i] = 25;
}
dp[i] = min + 1;
}
print(faces, n);
return dp[n];
}
static void print(int[] faces, int n) {
while (n > 0) {
System.out.println(faces[n]);
n -= faces[n];
}
}
优化- 适用于所有硬币情况
static int coins5(int n, int[] faces) {
if (n < 1 || faces == null || faces.length == 0) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int face : faces) {
if (i < face) continue;
min = Math.min(dp[i - face], min);
}
dp[i] = min + 1;
}
return dp[n];
}
优化- 找到则返回, 否则返回-1
static int coins(int n, int[] faces) {
if (n < 1 || faces == null || faces.length == 0) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int face : faces) {
if (i < face) continue;
int v = dp[i - face];
if (v < 0 || v >= min) continue;
min = v;
}
if (min == Integer.MAX_VALUE) {
dp[i] = -1;
} else {
dp[i] = min + 1;
}
}
return dp[n];
}
例2, 最大连续子序列和
一个长度为n 的整数序列, 求它的最大连续子序列和
-2, 1, -3, 4, -1, 2,1, -5, 4, 这组序列的最大连续子序列和为 4 + (-1) + 2 + 1 = 6
定义状态
假设dp(i) 是以nums[i] 结尾的最大连续子序列和, 则
- 以nums[0] -2 结尾的最大连续子序列和为 -2, 所以dp(0) = -2
- 以nums[1] 1 结尾的最大连续子序列和为 1, 所以dp(1) = 1
- 以nums[2] -3 结尾的最大连续子序列和为 1, -3, 所以dp(2) = dp(1) + -3 = -2
- 以nums[3] -4 结尾的最大连续子序列和为 4, 所以dp(3) = 4
- 以nums[4] -1 结尾的最大连续子序列和为 4, -1, 所以dp(4) = dp(3) + (-1) = 3
- 以nums[5] -2 结尾的最大连续子序列和为 4, -1, 2, 所以dp(5) = dp(4) + 2 = 5
- 以nums[6] 1 结尾的最大连续子序列和为 4, -1, 2, 1, 所以dp(6) = dp(5) + 1 = 6
- 以nums[7] -5 结尾的最大连续子序列和为 4, -1, 2, 1, -5, 所以dp(7) = dp(6) + (-5) = 1
- 以nums[8] 4 结尾的最大连续子序列和为 4, -1, 2, 1, -5, 4, 所以dp(8) = dp(7) + 4 = 5
状态转移方程为
- 如果dp(i - 1) <= 0, 那么dp(i) = nums[i]
- 如果dp(i - 1) > 0, 那么dp(i) = dp(i - 1) + nums[i]
初始状态
- dp(0) = nums[0]
最终解
- 最大连续子序列和是所有dp(i) 中最大值max{dp(i)}, i∈[0, nums.length)
//空间复杂度为O(n), 时间复杂度为O(n)
static int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < dp.length; i++) {
int prev = dp[i - 1];
if (prev <= 0) {
dp[i] = nums[i];
} else {
dp[i] = prev + nums[i];
}
max = Math.max(dp[i], max);
}
return max;
}
// 优化, 不适用数组, 直接使用变量dp, 计算只是用到了之前的一个值
// 空间复杂度为O(1), 时间复杂度为O(n)
static int maxSubArray2(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp = nums[0];
int max = dp;
for (int i = 1; i < nums.length; i++) {
if (dp <= 0) {
dp = nums[i];
} else {
dp = dp + nums[i];
}
max = Math.max(max, dp);
}
return max;
}
例3, 最长上升子序列(LIS)
一个无序整数序列, 求出它最长上升子序列长度, 严格上升
[10, 2, 2, 5, 1, 7, 101, 18], 最长上升子序列是[2, 5, 7, 101], 或者[2, 5, 7, 18], 长度为4
状态定义
加速数组为nums, [10, 2, 2, 5, 1, 7, 101, 18]
dp(i) 是以nums[i] 结尾的最长上升子序列长度, i ∈ [0, nums.length)
- 以nums[0] 10 结尾的最长上升子序列为 10, 所以dp(0) = 1
- 以nums[1] 1 结尾的最长上升子序列为 2, 所以dp(1) = 1
- 以nums[2] -3 结尾的最长上升子序列为 2, 所以dp(2) = 1
- 以nums[3] -4 结尾的最长上升子序列为 2, 5, 所以dp(3) = dp(1) + 1 = dp(2) + 1 = 2
- 以nums[4] -1 结尾的最长上升子序列为 1, 所以dp(4) = 1
- 以nums[5] -2 结尾的最长上升子序列为 2, 5, 7, 所以dp(5) = dp(3) + 1 = 3
- 以nums[6] 1 结尾的最长上升子序列为 2, 5, 7, 101, 所以dp(6) = dp(5) + 1 = 4
- 以nums[7] -5 结尾的最长上升子序列为 2, 5, 7, 18, 所以dp(7) = dp(5) + 1 = 4
所以最长上升子序列长度是所有dp(i) 中最大值max{dp(i)}, i ∈[0, nums.length)
状态转移方程
-
遍历j ∈[0, i)
-
当nums[i] > nums[j]
nums[i] 可以接在nums[j] 后面, 形成一个比dp(j) 更长的上升子序列, 长度为dp(j) + 1
dp(i) = max{dp(i), dp(j) + 1}
-
当nums[i] <= nums[j]
nums[i] 不能接在nums[j] 后面 跳过此前遍历
-
-
状态初始值
- dp(0) = 1
- 所有的dp(i) 默认都初始化为1
/**
* 动态规划
* 空间复杂度O(n), 时间复杂度O(n^2)
*/
static int lengthOfLIS1(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
int max = dp[0] = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] <= nums[j]) continue;
dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(dp[i], max);
}
return max;
}
例4, 最长公共子序列(LCS)
例如
[1, 2, 5, 9, 10], 和[1, 4, 9, 10] 最长公共子序列为[1, 9, 10] 长度为3
ABCBDAB 和BDCABA 最长公共子序列长度为4
BDAB, BCAB, BCBA 为公共子序列
思路:
假设dp(i, j) 是nums1 前i 个元素与nums2 前j 个元素的最长公共子序列长度
- dp(i, 0) dp(0, j) 初始值为0
- 如果nums1[i - 1] = nums2[j - 1], 那么dp(i, j) = dp(i - 1, j - 1) + 1
- 如果nums1[i - 1] ≠ nums2[j - 1], 那么dp(i, j) = max{dp(i - 1, j), dp(i, j - 1)}
使用递归实现
/**
* 使用递归, 求nums1 前i 个元素, 和nums2 前j 个元素的最长公共子序列长度
* @param nums1
* @param nums2
* @return
*/
static int lcs1(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return 0;
if (nums2 == null || nums2.length == 0) return 0;
return lcs1(nums1, nums1.length, nums2, nums2.length);
}
static int lcs1(int[] nums1, int i, int[] nums2, int j) {
if (i == 0|| j == 0) return 0;
if (nums1[i - 1] == nums2[j - 1]) {
return lcs1(nums1, i - 1, nums2, j - 1) + 1;
}
return Math.max(lcs1(nums1, i - 1, nums2, j),
lcs1(nums1, i, nums2, j - 1));
}
空间复杂度O(k), k = min{n, m}, n, m 是2 个序列的长度
时间复杂度O(2^n), 当n = m 时
递归过程
使用递归, 计算过程中出现了很多重复的计算
使用非递归实现
static int lcs2(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return 0;
if (nums2 == null || nums2.length == 0) return 0;
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[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[nums1.length][nums2.length];
}
空间复杂度O(n * m)
时间复杂度O(n * m)
数组的计算结果如下, 使用了二维数组, 空间复杂度较高
最长公共子序列非递归
优化, 使用滚动数组优化空间
/**
* 使用两行数组
* @param nums1
* @param nums2
* @return
*/
static int lcs3(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return 0;
if (nums2 == null || nums2.length == 0) return 0;
int[][] dp = new int[2][nums2.length + 1];
for (int i = 1; i <= nums1.length; i++) {
int row = i & 1;
int preRow = (i - 1) & 1;
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[row][j] = dp[preRow][j - 1] + 1;
} else {
dp[row][j] = Math.max(dp[preRow][j], dp[row][j - 1]);
}
}
}
return dp[nums1.length & 1][nums2.length];
}
再优化, 使用一个一维数组
/**
* 使用一维数组, cur 记录之前一行的前一个数据
* @param nums1
* @param nums2
* @return
*/
static int lcs4(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return 0;
if (nums2 == null || nums2.length == 0) return 0;
int[] dp = new int[nums2.length + 1];
for (int i = 1; i <= nums1.length; i++) {
int cur = 0;
for (int j = 1; j <= nums2.length; j++) {
int leftTop = cur;
cur = dp[j];
if (nums1[i - 1] == nums2[j - 1]) {
dp[j] = leftTop + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
}
}
return dp[nums2.length];
}
再优化, 选取长度小的作为列
空间复杂度优化到O(k), k = min{n, m}
/**
* 缩短一维数组的长度
* @param nums1
* @param nums2
* @return
*/
static int lcs5(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return 0;
if (nums2 == null || nums2.length == 0) return 0;
int[] rowsNums = nums1, colsNums = nums2;
if (nums1.length < nums2.length) {
colsNums = nums1;
rowsNums = nums2;
}
int[] dp = new int[colsNums.length + 1];
for (int i = 1; i <= rowsNums.length; i++) {
int cur = 0;
for (int j = 1; j <= colsNums.length; j++) {
int leftTop = cur;
cur = dp[j];
if (rowsNums[i - 1] == colsNums[j - 1]) {
dp[j] = leftTop + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
}
}
return dp[colsNums.length];
}
例5, 最长公共子串
子串是连续的子序列
例如
ABCBA, 和BABCA 的最长公共子串是ABC, 长度为3
思路:
假设2 个字符串分别为str1, str2
- i ∈ [1, str1.length]
- j ∈ [1, str2.length]
假设dp(i, j) 是以str1[i - 1], str2[j - 1] 结尾的最长公共子串长度
- dp(i, 0) dp(0, j) 初始值都为0
- 如果str1[i - 1] = str2[j - 1], 那么dp(i, j) = dp(i - 1, j - 1) + 1
- 如果str1[i - 1] ≠ str2[j - 1], 那么dp(i, j) = 0
最长公共子串长度是所有dp(i, j) 中最大值max{dp(i, j)}
/**
* 最长公共子串, 二维数组, 实际只用到之前一组数据
* @param str1
* @param str2
* @return
*/
static int lcs1(String str1, String str2) {
if (str1 == null || str2 == null) return 0;
char[] chars1 = str1.toCharArray();
if (chars1.length == 0) return 0;
char[] chars2 = str2.toCharArray();
if (chars2.length == 0) return 0;
int[][] dp = new int[chars1.length + 1][chars2.length + 1];
int max = 0;
for (int i = 1; i <= chars1.length; i++) {
for (int j = 1; j <= chars2.length; j++) {
if (chars1[i - 1] != chars2[j - 1]) continue;
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(dp[i][j], max);
}
}
return max;
}
优化, 使用一维数组
/**
* 使用一维数组, cur 记录之前左上角的值, 用于下次比较
* @param str1
* @param str2
* @return
*/
static int lcs2(String str1, String str2) {
if (str1 == null || str2 == null) return 0;
char[] chars1 = str1.toCharArray();
if (chars1.length == 0) return 0;
char[] chars2 = str2.toCharArray();
if (chars2.length == 0) return 0;
char[] rowsChars = chars1, colsChars = chars2;
if (chars1.length < chars2.length) {
colsChars = chars1;
rowsChars = chars2;
}
int[] dp = new int[colsChars.length + 1];
int max = 0;
for (int row = 1; row <= rowsChars.length; row++) {
int cur = 0;
for (int col = 1; col <= colsChars.length; col++) {
int leftTop = cur;
cur = dp[col];
if (chars1[row - 1] != chars2[col - 1]) {
dp[col] = 0;
} else {
dp[col] = leftTop + 1;
max = Math.max(dp[col], max);
}
}
}
return max;
}
优化, 数组从后往前遍历
/**
* 从后往前遍历, 第一遍遍历时已经存储相关值, 逐个对比即可
* @param str1
* @param str2
* @return
*/
static int lcs(String str1, String str2) {
if (str1 == null || str2 == null) return 0;
char[] chars1 = str1.toCharArray();
if (chars1.length == 0) return 0;
char[] chars2 = str2.toCharArray();
if (chars2.length == 0) return 0;
char[] rowsChars = chars1, colsChars = chars2;
if (chars1.length < chars2.length) {
colsChars = chars1;
rowsChars = chars2;
}
int[] dp = new int[colsChars.length + 1];
int max = 0;
for (int row = 1; row <= rowsChars.length; row++) {
for (int col = colsChars.length; col >= 1; col--) {
if (chars1[row - 1] != chars2[col - 1]) {
dp[col] = 0;
} else {
dp[col] = dp[col - 1] + 1;
max = Math.max(dp[col], max);
}
}
}
return max;
}
例6, 0-1 背包问题
0-1 背包问题使用动态规划求解
在保证总重量不超过W 的前提下, 选择某些物品装入背包, 背包的最大总价值是多少
每个物品只有1 件, 也就是每个物品只能选择0, 或者1 件
- 假设values 是价值数组, weights 为重量数组
- 编号为k 的物品, 价值是values[k], 重量是weights[k], k ∈ [0, n)
- 假设dp(i, j) 是最大承重为j, 有前i 件物品可选时的最大总价值, i ∈ [1, n], j ∈[1, W]
- dp(i, 0), dp(0, j) 初始值为0
- 如果j < weights[i - 1], 那么dp(i, j) = dp(i - 1, j)
- 如果j >= weights[i - 1], 那么dp(i, j) = max{dp(i - 1, j), dp(i - 1, j - weights[i - 1]) + values[i - 1]}
/**
* 背包0-1,
* @param values
* @param weights
* @param capacity
* @return
*/
static int maxValue1(int[] values, int[] weights, int capacity) {
if (values == null || values.length == 0) return 0;
if (weights == null || weights.length == 0) return 0;
if (values.length != weights.length || capacity <= 0) return 0;
int[][] dp = new int[values.length + 1][capacity + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = 1; j <= capacity; j++) {
if (j < weights[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(
dp[i - 1][j],
values[i - 1] + dp[i - 1][j - weights[i - 1]]);
}
}
}
return dp[values.length][capacity];
}
二维数组的计算过程
01背包
优化, 使用一维数组
dp(i, j) 都是由dp(i - 1, k) 推导出来的, 也就是说, 第i 行的数据是由它的上一行第i - 1行推导出来的, 因此可以使用一维数组优化
static int maxValue2(int[] values, int[] weights, int capacity) {
if (values == null || values.length == 0) return 0;
if (weights == null || weights.length == 0) return 0;
if (values.length != weights.length || capacity <= 0) return 0;
int[] dp = new int[capacity + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = capacity; j >= 1; j--) {
if (j < weights[i - 1]) continue;
dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
}
}
return dp[capacity];
}
/**
* 继续优化, 遍历到j 的值小于当前可选值的大小, 后续遍历都不可选择当前的价值
* @param values
* @param weights
* @param capacity
* @return
*/
static int maxValue4(int[] values, int[] weights, int capacity) {
if (values == null || values.length == 0) return 0;
if (weights == null || weights.length == 0) return 0;
if (values.length != weights.length || capacity <= 0) return 0;
int[] dp = new int[capacity + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = capacity; j >= weights[i - 1]; j--) {
dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
}
}
return dp[capacity];
}
如果恰好装满
- dp(i, j) 初 始状态调整
- dp(i, 0) = 0, 总重量恰好为0, 最大总价值必然也是0
- dp(0, j) = -∞, j >= 1, 负数代表无法装满
01背包恰好装满
/**
* 恰好装满的状态
* @param values
* @param weights
* @param capacity
* @return
*/
static int maxValueExactly(int[] values, int[] weights, int capacity) {
if (values == null || values.length == 0) return 0;
if (weights == null || weights.length == 0) return 0;
if (values.length != weights.length || capacity <= 0) return 0;
int[] dp = new int[capacity + 1];
for (int j = 1; j <= capacity; j++) {
dp[j] = Integer.MIN_VALUE;
}
for (int i = 1; i <= values.length; i++) {
for (int j = capacity; j >= weights[i - 1]; j--) {
dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
}
}
return dp[capacity] < 0 ? -1 : dp[capacity];
}
