目录
动态规划（Dynamic Programming）
动态规划的常规步骤
动态规划的一些相关概念
无后效性
有后效性
算法1 – 找零钱
问题
状态定义
题解 – 暴力递归
题解 – 记忆化搜索
题解 – 递推
思考题: 请输出找零钱的具体方案 (具体是用了哪些面值的硬币)
题解 – 通用实现优化
算法2 – 最大连续子序列和
问题
状态定义
状态转移方程和初始状态
题解 – 动态规划 – 实现
题解 – 动态规划 – 优化实现
算法3 – 最长上升子序列 (LIS)
问题
状态定义
状态转移方程
题解 – 动态规划 – 实现
题解 – 耐心排序 – 思路
题解 – 耐心排序 – 实现
题解 – 耐心排序 – 二分搜索 – 思路
题解 – 耐心排序 – 二分搜索 – 实现
算法4 – 最长公共子序列 (LCS)
问题
思路
题解 – 递归实现
递归实现分析
题解 – 非递归实现
题解 – 非递归实现 – 滚动数组优化
题解 – 非递归实现 – 一维数组优化
题解 – 非递归实现 – 一维数组优化 – 空间复杂度优化
算法5 – 最长公共子串
问题
思路
题解 – 实现
题解 – 一维数组优化
题解 – 一维数组优化 – 空间复杂度优化
题解 – 一维数组优化 – 空间复杂度优化 – 逆序优化
算法6 – 0-1背包
问题
题解 – 实现 – 二维数组
题解 – 实现 – 一维数组 – 倒序优化
题解 – 实现 – 循环优化
0-1背包 – 恰好装满
问题
思路
实现
动态规划（Dynamic Programming）
动态规划，简称DP, 是求解最优化问题的一种常用策略
通常的使用规则 (一步一步优化)
- 暴力递归 (自顶向下，出现了重叠子问题)
- 记忆化搜索 (自顶向下)
- 递推 (自底向上)
动态规划的常规步骤
动态规划中的 “动态” 可以理解为是“会变化的状态”
- 定义状态 (状态是原问题、子问题的解) 比如定义 dp(i) 的含义
- 设置初始状态 (边界) 比如设置 dp(0) 的值
- 确定状态转移方程 比如确定 dp(i) 和 dp(i – 1) 的关系, 即已知dp(i-1), 如果推算出dp(i) 或者已知dp(i), 如何推算出dp(i-1)
动态规划的一些相关概念
来自维基百科的解释: Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
- 将复杂的原问题拆解成若干个简单的子问题
- 每个子问题仅仅解决1次，并保存它们的解
- 最后推导出原问题的解
可以用动态规划来解决的问题，通常具备2个特点:
(1) 最优子结构(最优化原理): 通过求解子问题的最优解, 可以获得原问题的最优解
(2) 无后效性
a. 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响（未来与过去无关）
b. 在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的
无后效性
问题: 从起点(0, 0)走到终点(4, 4)一共有多少种走法？只能向右、向下走
假设 dp(i, j) 是从(0, 0)走到(i, j)的走法:
dp(i, 0) = dp(0, j) = 1
dp(i, j) = dp(i, j – 1) + dp(i – 1, j)
无后效性: 推导 dp(i, j) 时只需要用到 dp(i, j – 1)、dp(i – 1, j) 的值, 不需要关心 dp(i, j – 1)、dp(i – 1, j) 的值是怎么求出来的
有后效性
问题: 从起点(0, 0)走到终点(4, 4)一共有多少种走法？可以向左、向右、向上、向下走，但是同一个格子不能走 2 次
有后效性: dp(i, j) 下一步要怎么走，还要关心上一步是怎么来的, 也就是还要关心 dp(i, j – 1)、dp(i – 1, j) 是怎么来的？因为, 每个格子只能走1次, 那么在dp(i, j)后面的步骤中需要考虑dp(i, j)前面的步骤, 不能重复走同一个格子
算法1 – 找零钱
LeetCode: leetcode_322_零钱兑换
问题
假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
此前用贪心策略得到的并非是最优解 (贪心得到的解是 5 枚硬币)
状态定义
假设 dp(n) 是凑到 n 分需要的最少硬币个数
- 如果第 1 次选择了 25 分的硬币，那么 dp(n) = dp(n – 25) + 1
- 如果第 1 次选择了 20 分的硬币，那么 dp(n) = dp(n – 20) + 1
- 如果第 1 次选择了 5 分的硬币，那么 dp(n) = dp(n – 5) + 1
- 如果第 1 次选择了 1 分的硬币，那么 dp(n) = dp(n – 1) + 1
所以 dp(n) = min { dp(n – 25), dp(n – 20), dp(n – 5), dp(n – 1) } + 1
题解 – 暴力递归
/**
* 暴力解决
* @param n
* @return
*/
static int coinChange(int n){
if(n <= 0) return Integer.MAX_VALUE;
if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
/**
* 找一枚硬币, 剩下零钱需要最少的硬币数量
* 当前找的这枚硬币可以是25, 20, 5, 1;
*/
int min1 = Math.min(coinChange(n - 25),coinChange(n - 20));
int min2 = Math.min(coinChange(n - 5),coinChange(n - 1));
//确认找哪种硬币后, 总找硬币数量加一
return Math.min(min1,min2) + 1;
}
类似于斐波那契数列的递归版，会有大量的重复计算，时间复杂度较高
题解 – 记忆化搜索
/**
* 记忆化搜索
*/
static int coinChange1(int n){
if(n < 1) return -1;
int[] coins = new int[n + 1];
for (int i = 0; i < coins.length; i++) {
if(i == 25) coins[i] = 1;
if(i == 20) coins[i] = 1;
if(i == 5) coins[i] = 1;
if(i == 1) coins[i] = 1;
}
return coinChange1(n,coins);
}
static int coinChange1(int n, int[] coins){
if(n <= 0) return Integer.MAX_VALUE;
//如果待找零钱的最少硬币数量已计算出来, 则直接返回
if(coins[n] != 0) return coins[n];
/**
* 找一枚硬币, 剩下零钱需要最少的硬币数量
* 当前找的这枚硬币可以是25, 20, 5, 1;
*/
int min1 = Math.min(coinChange1(n - 25,coins),coinChange1(n - 20,coins) );
int min2 = Math.min(coinChange1(n - 5,coins),coinChange1(n - 1,coins) );
//当前零钱已确认找哪种硬币后, 总找硬币数量加一, 并且暂存于在数组中
coins[n] = Math.min(min1,min2) + 1;
return coins[n];
}
题解 – 递推
/**
* 递推
* @param n
* @return
*/
static int coinChange3(int n){
if(n <= 0) return Integer.MAX_VALUE;
int[] coins = new int[n+1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
if(i >= 1) min = Math.min(min,coins[i - 1]);
if(i >= 5) min = Math.min(min,coins[i - 5]);
if(i >= 20) min = Math.min(min,coins[i - 20]);
if(i >= 25) min = Math.min(min,coins[i - 25]);
coins[i] = min + 1;
}
return coins[n];
}
思考题: 请输出找零钱的具体方案 (具体是用了哪些面值的硬币)
/**
* 递推
* @param n
* @return
*/
static int coinChange3(int n){
if(n <= 0) return Integer.MAX_VALUE;
int[] coins = new int[n+1];
//faces[i]是凑够i分时最后那枚硬币的面值
int[] faces = new int[coins.length];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
if(i >= 1){
min = Math.min(min,coins[i - 1]);
faces[i] = 1;
}
if(i >= 5){
min = Math.min(min,coins[i - 5]);
faces[i] = 5;
}
if(i >= 20){
min = Math.min(min,coins[i - 20]);
faces[i] = 20;
}
if(i >= 25){
min = Math.min(min,coins[i - 25]);
faces[i] = 25;
}
coins[i] = min + 1;
print(faces,i);
}
return coins[n];
}
static void print(int[] faces, int n){
System.out.print("零钱:"+n+", 应找硬币:");
while(n > 0){
//输出凑够n分时,所需要的硬币面值
System.out.print(faces[n] + " ");
//计算凑够剩下零钱所需要的硬币
n -= faces[n];
}
System.out.println();
}
题解 – 通用实现优化
static int coinChange4(int n, int[] faces){
if(n <= 0) return Integer.MAX_VALUE;
int[] coins = new int[n+1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int face : faces) {
if(i < face) continue;
if(coins[i-face] < 0) continue; //如果使用面值为face的硬币后, 剩余的零钱无法找到合适的硬币, 那么当前零钱也无法找回
min = Math.min(coins[i - face], min);
}
//如果i没有找到合适的硬币, 那么返回-1
if (min == Integer.MAX_VALUE){
coins[i] = -1;
}else{
coins[i] = min + 1;
}
}
return coins[n];
}
算法2 – 最大连续子序列和
问题
给定一个长度为 n 的整数序列，求它的最大连续子序列和
比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6
状态定义
假设 dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）
- 以 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)
题解 – 动态规划 – 实现
/**
* 最大连续子序列
* 示例: {–2, 1, –3, 4, –1, 2, 1, –5, 4 }
*/
static int maxSubArray(int[] nums){
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
int max = dp[0] = nums[0]; //以dp[0]结尾的最大子序列的值为nums[0], max默认为dp[0]
for (int i = 1; i < nums.length; i++) {
/**
* 如果以dp[i-1]结尾的最大子序列的值大于0, 那么以dp[i]结尾的最大子序列为: 以dp[i-1]结尾的最大子序列 + nums[i];
* 否则, 以dp[i]结尾的最大子序列为: nums[i]
*/
if(dp[i-1] > 0){
dp[i] = dp[i-1] + nums[i];
}else{
dp[i] = nums[i];
}
max = Math.max(max,dp[i]);
}
return max;
}
空间复杂度:O(n), 时间复杂度: O(n)
题解 – 动态规划 – 优化实现
/**
* 最大连续子序列 -- 优化
* 仅使用dp变量, 而不是数组; dp为以nums[i-1]结尾的最大子序列的值
*
* 示例: {–2, 1, –3, 4, –1, 2, 1, –5, 4 }
*/
static int maxSubArray2(int[] nums){
if(nums == null || nums.length == 0) return 0;
int dp = nums[0];
int max = dp; //以dp[0]结尾的最大子序列的值为nums[0], max默认为dp[0]
for (int i = 1; i < nums.length; i++) {
/**
* 如果以nums[i-1]结尾的最大子序列(原dp)的值大于0, 那么以nums[i]结尾的最大子序列(新dp)为: 以nums[i-1]结尾的最大子序列(原dp) + nums[i];
* 否则, 以nums[i]结尾的最大子序列(新dp)为: nums[i]
*/
if(dp > 0){
dp = dp + nums[i];
}else{
dp = nums[i];
}
max = Math.max(max,dp);
}
return max;
}
空间复杂度: O(1), 时间复杂度: O(n)
算法3 – 最长上升子序列 (LIS)
最长上升子序列 (最长递增子序列, Longest Increasing Subsequence, LIS)
LeetCode: leetcode_300_最长上升子序列
问题
给定一个无序的整数序列，求出它最长上升子序列的长度 (要求严格上升)
比如 [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] 2 结尾的最长上升子序列是 2，所以 dp(1) = 1
- 以 nums[2] 2 结尾的最长上升子序列是 2，所以 dp(2) = 1
- 以 nums[3] 5 结尾的最长上升子序列是 2、5，所以 dp(3) = dp(1) + 1 = dp(2) + 1 = 2
- 以 nums[4] 1 结尾的最长上升子序列是 1，所以 dp(4) = 1
- 以 nums[5] 7 结尾的最长上升子序列是 2、5、7，所以 dp(5) = dp(3) + 1 = 3
- 以 nums[6] 101 结尾的最长上升子序列是 2、5、7、101，所以 dp(6) = dp(5) + 1 = 4
- 以 nums[7] 18 结尾的最长上升子序列是 2、5、7、18，所以 dp(7) = dp(5) + 1 = 4
最长上升子序列的长度是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)
状态转移方程
遍历 j ∈ [0, i)
1. 当 nums[i] > nums[ j]
nums[i] 可以接在 nums[ j] 后面，形成一个比 dp( j) 更长的上升子序列，长度为 dp( j) + 1
dp(i) = max { dp(i), dp( j) + 1 }
2. 当 nums[i] ≤ nums[ j]
nums[i] 不能接在 nums[ j] 后面，跳过此次遍历（continue）
3. 状态的初始值
dp(0) = 1
所有的 dp(i) 默认都初始化为 1
题解 – 动态规划 – 实现
/**
* 最长上升子序列 -- 动态规划
* 示例:{10, 2, 3, 5, 1, 7, 101, 18}
*/
static int lis(int[] nums){
if(nums == null || nums.length == 0) return 0;
int[] dp = new int[nums.length];
int max = dp[1] = 1;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
/**
* 每个nums[i]都需要跟前[0,i)范围内的所有以nums[j]结尾的最长上升子序列(dp[i])进行比较,
* 如果nums[i]的值大于nums[j], 那么以nums[i]结尾的最长上升子序列为: 以nums[j]结尾的最长上升子序列(dp[i]) + 1;
* 否则,以nums[i]结尾的最长上升子序列为:nums[i];
*
* 在计算以nums[i]的最长上升子序列时, 需要比较当前已计算出的dp[i]与dp[j]+1的大小, 取较大值
*/
for (int j = 0; j < i; j++) {
if(nums[i] > nums[j]){
//例: Math.max(dp[5],dp[3] + 1) 注意此时dp[5] = dp[2] + 1;
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
max = Math.max(max,dp[i]);
}
return max;
}
空间复杂度: O(n), 时间复杂度: O(n^2)
题解 – 耐心排序 – 思路
1. 把每个数字看做是一张扑克牌，从左到右按顺序处理每一个扑克牌
2. 将它压在(从左边数过来)第一个牌顶 ≥ 它的牌堆上面
3. 如果找不到牌顶 ≥ 它的牌堆, 就在最右边新建一个牌堆, 将它放入这个新牌堆中
4. 当处理完所有牌，最终牌堆的数量就是最长上升子序列的长度
为什么最终牌堆的数量就是最长上升子序列的长度?
根据摆放规则可以推出:
第n个堆的堆顶元素A, 在第n-1个堆中, 一定存在一个元素B, 元素B大于A且在原始数组中 A 排在B的前面; 只有B大于A, 才导致摆放B时需要重新建堆, 并且, 如果在原始数组中 A 排在B的后面且B大于A, 那么A与B将放在一个堆中, 所以堆的数量就是最长上升子序列的长度
题解 – 耐心排序 – 实现
/**
* 最长上升子序列 -- 耐心排序优化
* @param nums
* @return
*/
static int lis2(int[] nums){
if(nums == null || nums.length == 0) return 0;
//牌堆的数量
int len = 0;
//牌顶数组
int[] top = new int[nums.length];
for (int num : nums) {
int j = 0;
while(j < len){
if(top[j] >= num){
top[j] = num;
break;
}
//牌顶 < num
j++;
}
if(j == len){ //新建一个堆顶
len++;
top[j] = num;
}
}
return len;
}
题解 – 耐心排序 – 二分搜索 – 思路
假设数组是 nums，也就是最初的牌数组:
1. top[i] 是第 i 个牌堆的牌顶，len 是牌堆的数量，初始值为 0
2. 遍历每一张牌 num
(1) 利用二分搜索找出 num 最终要放入的牌堆位置 index
(2) num 作为第 index 个牌堆的牌顶，top[index] = num
(3) 如果 index 等于 len，相当于新建一个牌堆，牌堆数量 +1，也就是 len++
题解 – 耐心排序 – 二分搜索 – 实现
/**
* 最长上升子序列 -- 耐心排序优化 --二分搜索优化
* 时间复杂度 O(nlogn)
* @param nums
* @return
*/
static int lis3(int[] nums){
if(nums == null || nums.length == 0) return 0;
//牌堆的数量
int len = 0;
//牌顶数组
int[] top = new int[nums.length];
for (int num : nums) {
int begin = 0;
int end = len;
while (begin < end) {
int mid = (begin + end) >> 1;
if (num <= top[mid]) {
end = mid;
} else {
begin = mid + 1;
}
}
// 覆盖牌顶
top[begin] = num;
// 检查是否要新建一个牌堆
if (begin == len) len++;
}
return len;
}
空间复杂度: O(n), 时间复杂度: O(nlogn)
算法4 – 最长公共子序列 (LCS)
最长公共子序列 (Longest Common Subsequence，LCS)
LeetCode: leetcode_1143_最长公共子序列
问题
求两个序列的最长公共子序列长度
例: [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3
ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，可能是
ABCBDAB 和 BDCABA > BDAB
ABCBDAB 和 BDCABA > BDAB
ABCBDAB 和 BDCABA > BCAB
ABCBDAB 和 BDCABA > BCBA
思路
1. 假设 2 个序列分别是 nums1、nums2 (i ∈ [1, nums1.length], j ∈ [1, nums2.length] )
2. 假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
a. dp(i, 0)、dp(0, j) 初始值均为 0
b. 如果 nums1[i – 1] = nums2[ j – 1], 那么 dp(i, j) = dp(i – 1, j – 1) + 1
c. 如果 nums1[i – 1] ≠ nums2[ j – 1], 那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }
题解 – 递归实现
/**
* 最长公共子序列 (递归)
*/
static int lcs(int[] nums1, int[] nums2){
if(nums1 == null || nums1.length == 0) return 0;
if(nums2 == null || nums2.length == 0) return 0;
return lcs(nums1,nums1.length,nums2,nums2.length);
}
/**
* @param nums1 数组1
* @param i 数组1中前i个元素: [0,i-1]
* @param nums2 数组2
* @param j 数组2中前j个元素:[0,j-1]
* @return
*/
static int lcs(int[] nums1, int i, int[] nums2, int j){
if(i == 0 || j == 0) return 0;
if(nums1[i-1] != nums2[j-1]){
/**
* 此处递归的意义在于:
* 如果数组nums1的第i-1个元素与数组nums2的第j-1个元素不相等, 那么
* 1. 比对数组nums1的前i-1个元素与数组nums2的前j个元素, 存在的最长公共子序列
* 2. 比对数组nums1的前i个元素与数组nums2的前j-1个元素, 存在的最长公共子序列
* 在到达递归基后的逻辑可以理解为, 遍历数组nums1每个元素, 去比对数组nums2的每一个元素,如果存在相同的, 则公共子序列数量加一
*/
return Math.max(
lcs(nums1,i-1,nums2,j),
lcs(nums1,i,nums2,j-1));
}
return lcs(nums1,i-1,nums2,j-1) + 1;
}
空间复杂度: O(k), k = min{n, m}, n、m 是2个序列的长度
时间复杂度: O(2n), 当 n = m 时
递归实现分析
出现重复递归调用
题解 – 非递归实现
/**
* 最长公共子序列 (非递归)
* @param nums1
* @param nums2
* @return
*/
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++) {
/**
* 遍历nums1中的每一个元素, 与nums2中进行比较
* 如果相同, 则更新dp[i][j]的值 (dp[i][j]表示nums1数组前i个元素与nums2数组前j个元素存在的最长公共子序列长度)
* 如果不同, 则比较 nums1数组前i个元素与nums2数组前j-1个元素存在的最长公共子序列长度
* 和 nums1数组前i-1个元素与nums2数组前j个元素存在的最长公共子序列长度
* 取较大的值
*/
for (int j = 1; j <= nums2.length; j++) {
if(nums1[i-1] == nums2[j-1]){ //i与j的含义为数组的前i个元素,前j个元素, 不包含第i,j个元素
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)
dp 数组的计算结果如下所示:
题解 – 非递归实现 – 滚动数组优化
使用滚动数组优化空间复杂度
/**
* 最长公共子序列 (非递归 -- 滚动数组优化)
* @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++) {
/**
* 遍历nums1中的每一个元素, 与nums2中进行比较
* 如果相同, 则更新dp[i][j]的值 (dp[i][j]表示nums1数组前i个元素与nums2数组前j个元素存在的最长公共子序列长度)
* 如果不同, 则比较 nums1数组前i个元素与nums2数组前j-1个元素存在的最长公共子序列长度
* 和 nums1数组前i-1个元素与nums2数组前j个元素存在的最长公共子序列长度
* 取较大的值
*/
int row = i & 1; // i % 2; ==取模优化==>>i & 1;
int prevRow = (i-1) & 1;// (i-1) % 2; ==取模优化==>>(i-1) & 1;
for (int j = 1; j <= nums2.length; j++) {
if(nums1[i - 1] == nums2[j-1]){ //i与j的含义为数组的前i个元素,前j个元素, 不包含第i,j个元素
dp[row][j] = dp[prevRow][j-1] + 1;
}else{
dp[row][j] = Math.max(dp[prevRow][j],dp[row][j-1]);
}
}
}
return dp[nums1.length & 1][nums2.length];
}
题解 – 非递归实现 – 一维数组优化
/**
* 最长公共子序列 (非递归 -- 一维数组)
* @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;
/**
* 此时dp[j]代表计算到上一行中第j个元素时,存在公共子序列, 将dp[j]暂存于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;
//优化dp数组的长度, 使用nums1和nums2中较小的长度来初始化dp数组
int[] colsNums = nums2;
int[] rowsNums = nums1;
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;
/**
* 此时dp[j]代表计算到上一行中第j个元素时,存在公共子序列, 将dp[j]暂存于cur中, 当计算下一个元素时需要使用
*/
cur = dp[j];
if(nums1[i - 1] == rowsNums[j-1]){
dp[j] = leftTop + 1;
}else{
dp[j] = Math.max(dp[j],dp[j-1]);
}
}
}
return dp[colsNums.length];
}
算法5 – 最长公共子串
最长公共子串 (Longest Common Substring), 子串是连续的子序列
问题
求两个字符串的最长公共子串长度, ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3
思路
1. 假设 2 个字符串分别是 str1、str2
i ∈ [1, str1.length]
j ∈ [1, str2.length]
2. 假设 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
3. 最长公共子串的长度是所有 dp(i, j) 中的最大值 max { dp(i, j) }
题解 – 实现
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;
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++) {
/**
* 在计算chars1数组中前i个元素与chars2数组前j个元素时:
* 如果第i-1个元素与第j-1个元素相等, 那么公共子串的长度为chars1数组中前i-1个元素与chars2数组前j-1个元素的最长公共子串长度 + 1
*/
if(chars1[i-1] == chars2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
max = Math.max(dp[i][j], max);
}
}
return max;
}
空间复杂度: O(n ∗ m)
时间复杂度: O(n ∗ m)
dp 数组的计算结果如下所示
题解 – 一维数组优化
/**
* 最长公共子串优化 -- 一维数组
* @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;
int[] dp = new int[chars2.length+1];
int max = 0;
for (int i = 1; i <= chars1.length; i++) {
int cur = 0;
for (int j = 1; j <= chars2.length; j++) {
int leftTop = cur;
cur = dp[j];
if(chars1[i-1] == chars2[j-1]){
dp[j] = leftTop + 1;
}
max = Math.max(dp[j], max);
}
}
return max;
}
空间复杂度: O(k), k = min{n, m}, 时间复杂度: O(n ∗ m)
题解 – 一维数组优化 – 空间复杂度优化
/**
* 最长公共子串优化 -- 一维数组 -- 行列优化
* @param str1
* @param str2
* @return
*/
static int lcs3(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[] colsChars = chars2, rowsChars = chars1;
if(chars1.length < chars2.length){
colsChars = chars1;
rowsChars = chars2;
}
int[] dp = new int[colsChars.length+1];
int max = 0;
for (int i = 1; i <= rowsChars.length; i++) {
int cur = 0;
for (int j = 1; j <= colsChars.length; j++) {
int leftTop = cur;
cur = dp[j];
if(rowsChars[i-1] == colsChars[j-1]){
dp[j] = leftTop + 1;
}
max = Math.max(dp[j], max);
}
}
return max;
}
题解 – 一维数组优化 – 空间复杂度优化 – 逆序优化
/**
* 最长公共子串优化 -- 一维数组 -- 行列优化 -- 逆序优化
* @param str1
* @param str2
* @return
*/
static int lcs4(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[] colsChars = chars2, rowsChars = chars1;
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(rowsChars[row-1] == colsChars[col-1]){
dp[col] = dp[col-1] + 1;
}
max = Math.max(dp[col], max);
}
}
return max;
}
算法6 – 0-1背包
问题
1. 有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i
在保证总重量不超过 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？
注意：每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件
2. 假设 values 是价值数组，weights 是重量数组
编号为 k 的物品，价值是 values[k]，重量是 weights[k]，k ∈ [0, n)
3. 假设 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] }
题解 – 实现 – 二维数组
/**
* 二维数组
*/
static int maxValue(int[] values, int[] weights, int capacity){
if(values == null || values.length == 0) return 0;
if(weights == null || weights.length == 0) return 0;
if(weights.length != values.length) return 0;
if(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]){
/**
* 如果容量小于第i-1个物品的重量, 即背包容量无法再装入第i-1个物品
*/
dp[i][j] = dp[i-1][j];
}else{
/**
* 如果剩余容量大于等于第i-1个物品的重量, 那么此时有两个选择:
* 1.将第i-1件物品装入背包
* 2.不将第i-1件物品装入背包
* 取上面两种情况中的最大价值
*/
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weights[i-1]] + values[i-1]);
}
}
}
return dp[values.length][capacity];
}
dp 数组的计算结果如下所示:
题解 – 实现 – 一维数组 – 倒序优化
dp(i, j) 都是由 dp(i – 1, k) 推导出来的，也就是说，第 i 行的数据是由它的上一行第 i – 1 行推导出来的
因此，可以使用一维数组来优化
另外，由于 k ≤ j ，所以 j 的遍历应该由大到小，否则导致数据错乱
/**
* 一维数组 + 倒序优化
*/
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(weights.length != values.length) return 0;
if(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]){
dp[j] = Math.max(dp[j],dp[j-weights[i-1]] + values[i-1]);
}
}
}
return dp[capacity];
}
题解 – 实现 – 循环优化
观察二维数组表，得出结论：j 的下界可以从 1 改为 weights[i – 1]
/**
* 循环优化
*/
static int maxValue3(int[] values, int[] weights, int capacity){
if(values == null || values.length == 0) return 0;
if(weights == null || weights.length == 0) return 0;
if(weights.length != values.length) return 0;
if(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--) { // j的取值范围:[weights[i-1],capacity]
dp[j] = Math.max(dp[j],dp[j-weights[i-1]] + values[i-1]);
}
}
return dp[capacity];
}
0-1背包 – 恰好装满
问题
有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i
在保证总重量恰好等于 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？
注意: 每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件
思路
dp(i, j) 初始状态调整
dp(i, 0) = 0，总重量恰好为 0，最大总价值必然也为 0
dp(0, j) = –∞(负无穷)，j ≥ 1，负数在这里代表无法恰好装满
实现
/**
* 0-1背包问题 -- 恰好装满
*/
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(weights.length != values.length) return 0;
if(capacity <= 0) return 0;
int[] dp = new int[capacity + 1];
/**
* 初始化dp数组 注意:需要从1开始后的每一个值初始化为负无穷大
* 在初始化完成后, 数组中只有dp[0]为0, 那么意味着后续计算背包容量时
* 在所有情况中, 必须在装下物品后, 背包的容量为0时, 才可以计算出总价值 即,必须以dp[0]为初始值才可以计算出装物品的总价值
*/
for (int j = 1; j < dp.length; 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],dp[j-weights[i-1]] + values[i-1]);
}
}
return dp[capacity];
}