算法：【动态规划】
动态规划
一、背包问题
基本解题框架
1.1 01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
// 读入数据
Scanner reader = new Scanner(System.in);
// 物品的数量为 N
int N = reader.nextInt();
// 背包的容量为 V
int V = reader.nextInt();
// 一个长度为 N 的数组，第i个元素表示第i个物品的体积
int[] v = new int[N+1];
// 一个长度为 N 的数组，第i个元素表示第i个物品的价值
int[] w = new int[N+1];
for(int i=1; i<=N; i++){
v[i] = reader.nextInt();
w[i] = reader.nextInt();
}
reader.close();
// 正式工作的代码
/**
定义一个二阶矩阵dp[N+1][V+1],
这里之所以要N+1和V+1，是因为第0行表示只能选择第0个物品的时候，即没有物品的时候
第0列表示背包的体积为0的时候，即不能装任何东西的时候
dp[i][j]表示在 只能选择前i个物品，背包容量为j的情况下，背包中物品的最大价值
对于dp[i][j]有两种情况：
1. 不选择当前的第i件物品/第i件物品比背包容量要大，则dp[i][j] = dp[i-1][j]
2. 选择当前的第i件物品（潜在要求第i件物品体积小于等于背包总容量），则能装入的物品最大价值为：
当前物品的价值 加上 背包剩余容量在只能选前i-1件物品的情况下的最大价值
dp[i][j] = dp[i-1][j-v[i]] + w[i]
dp[i][j]在两种情况中选择比较大的情况作为当前的最优解；
即：
if(j >= v[i]):
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
else:
dp[i][j] = dp[i-1][j]
*/
int[][] dp = new int[N+1][V+1];
for(int i=1; i<=N; i++){
for(int j=0; j<=V; j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
}
}
System.out.println(dp[N][V]);
}
} 1.1.1 分割等和子集
class Solution {
// 0,1背包问题
public boolean canPartition(int[] nums) {
int sum=0, max=0;
for(int i=0; i<nums.length; i++){
sum += nums[i];
max = Math.max(max, nums[i]);
}
if(sum%2 != 0)
return false;
int ave = sum/2;
if(max > ave)
return false;
boolean[][] dp = new boolean[nums.length][ave+1];
for(int i=0; i<nums.length; i++)
dp[i][0] = true;
dp[0][nums[0]] = true;
for(int i=1; i<nums.length; i++){
for(int j=1; j<=ave; j++){
dp[i][j] = dp[i-1][j];
if(j >= nums[i]){
dp[i][j] = dp[i][j] || dp[i-1][j-nums[i]];
}
}
}
return dp[nums.length-1][ave];
}
}1.2 完全背包问题
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
// 物品种数
int N = reader.nextInt();
// 背包容量
int V = reader.nextInt();
// 长度为N的数组，第i个位置表示第i个物品的体积
int[] v = new int[N+1];
// 长度为N的数组，第i个位置表示第i个物品的价值
int[] w = new int[N+1];
for(int i=1; i<=N; i++){
v[i] = reader.nextInt();
w[i] = reader.nextInt();
}
reader.close();
// 暴力解法
int[][] dp = new int[N+1][V+1];
for(int i=1; i<=N; i++){
for(int j=0; j<=V; j++){
for(int k=0; j>=k*v[i]; k++){
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*v[i]] + k*w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}优化思路：
更新次序的内部关系：
有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：
for(int i=1; i<=N; i++)
for(int j=0; j<=V; j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]]+w[i]);
} 1.2.1 单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i=1; i<=s.length(); i++){
for(String word : wordDict){
int len = word.length();
if(i-len >=0 && word.equals(s.substring(i-len, i)))
dp[i] = dp[i] || dp[i-len];
}
}
return dp[s.length()];
}
}1.3 多重背包问题
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
// 物品种数
int N = reader.nextInt();
// 背包容量
int V = reader.nextInt();
// 体积数组
int[] v = new int[N+1];
// 价值数组
int[] w = new int[N+1];
// 每种物品的数量
int[] s = new int[N+1];
for(int i=1; i<=N; i++){
v[i] = reader.nextInt();
w[i] = reader.nextInt();
s[i] = reader.nextInt();
}
// 暴力解法
int[][] dp = new int[N+1][V+1];
for(int i=1; i<=N; i++){
for(int j=0; j<=V; j++){
for(int k=0; k<=s[i] && j>=k*v[i]; k++){
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k*v[i]] + k*w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}二进制优化
1.4 分组背包问题
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
基本思考框架
// 分组背包问题：枚举第i组物品选哪个
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
int MAX = 101;
// 物品种数
int N = reader.nextInt();
// 背包容量
int V = reader.nextInt();
// 体积数组
int[][] v = new int[MAX][MAX];
// 价值数组
int[][] w = new int[MAX][MAX];
int[] s = new int[MAX];
for(int i=1; i<=N; i++){
s[i] = reader.nextInt();
for(int j=0; j<s[i]; j++){
v[i][j] = reader.nextInt();
w[i][j] = reader.nextInt();
}
}
reader.close();
// 暴力解法
int[][] dp = new int[N+1][V+1];
for(int i=1; i<=N; i++){
for(int j=0; j<=V; j++){
dp[i][j] = dp[i-1][j];
for(int k=0; k<s[i]; k++){
if(j>=v[i][k])
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i][k]]+w[i][k]);
}
}
}
System.out.println(dp[N][V]);
}
}二、线性DP
2.1 数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
// 三角形的层数
int n = reader.nextInt();
// 三角形中的整数数组
int[][] values = new int[501][501];
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
values[i][j] = reader.nextInt();
}
}
int res = 0;
int[][] dp = new int[501][501];
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++)
dp[i][j] = Integer.MIN_VALUE;
}
dp[1][1] = values[1][1];
for(int i=2; i<=n; i++){
for(int j=1; j<=i; j++){
dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j])+ values[i][j];
}
}
for(int i=1; i<=n; i++){
res = Math.max(res, dp[n][i]);
}
System.out.println(res);
}
}2.2 最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] nums = new int[n];
for(int i=0; i<n; i++){
nums[i] = reader.nextInt();
}
int[] dp = new int[n];
int res = 0;
for(int i=0; i<n; i++){
dp[i] = 1; // 找不到前面数字小于自己的时候就为1
for(int j=0; j<i; j++){
if(nums[i] > nums[j]) // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
dp[i] = Math.max(dp[i], dp[j]+1);
}
res = Math.max(res, dp[i]);
}
System.out.println(res);
}
}2.3 最长公共子序列
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入样例：
4 5
acbd
abedc
输出样例：
3
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
int N = reader.nextInt();
int M = reader.nextInt();
char[] ch1 = reader.next().toCharArray();
char[] ch2 = reader.next().toCharArray();
int[][] dp = new int[N+1][M+1];
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++){
if(ch1[i-1] == ch2[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]);
}
System.out.println(dp[N][M]);
}
}2.4 最短编辑距离
给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：
- 删除–将字符串 A 中的某个字符删除。
- 插入–在字符串 A 的某个位置插入某个字符。
- 替换–将字符串 A 中的某个字符替换为另一个字符。现在请你求出，
将 A 变为 B 至少需要进行多少次操作。
输入样例：
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例：
4
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
char[] ch1 = reader.next().toCharArray();
int m = reader.nextInt();
char[] ch2 = reader.next().toCharArray();
int[][] dp = new int[n+1][m+1];
for(int i=0; i<=m; i++){
dp[0][i] = i;
}
for(int i=0; i<=n; i++)
dp[i][0] = i;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
int tmp = 0;
if(ch1[i-1] != ch2[j-1])
tmp = 1;
dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + tmp);
}
}
System.out.println(dp[n][m]);
}
}import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
char[] ch1 = reader.next().toCharArray();
int m = reader.nextInt();
char[] ch2 = reader.next().toCharArray();
int[][] dp = new int[n+1][m+1];
for(int i=0; i<=m; i++){
dp[0][i] = i;
}
for(int i=0; i<=n; i++)
dp[i][0] = i;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
int tmp = 0;
if(ch1[i-1] != ch2[j-1])
tmp = 1;
dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + tmp);
}
}
System.out.println(dp[n][m]);
}
}三、区间DP
区间 DP 常用模版
所有的区间dp问题，第一维都是枚举区间长度，一般 len = 1 用来初始化，枚举从 len = 2 开始，第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）
for (int i = 1; i <= n; i++) {
dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++) //区间长度
for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
int j = i + len - 1; //区间终点
for (int k = i; k < j; k++) { //枚举分割点，构造状态转移方程
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}3.1 石子合并
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。输入样例：
4
1 3 5 2
输出样例：
22
基本思考框架
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
int N = reader.nextInt();
int[] nums = new int[301];
int[] s = new int[N+1];
for(int i=1; i<=N; i++){
nums[i] = reader.nextInt();
s[i] += s[i-1] + nums[i];
}
int[][] dp = new int[301][301];
// 区间 DP 枚举套路：长度+左端点
for(int len=1; len<=N; len++) // len表示i和j堆下标的差值
for(int i=1; i+len<=N; i++){
int j = i+len; // 自动得到右端点
dp[i][j] = Integer.MAX_VALUE;
for(int k=i; k<j; k++){
dp[i][j] = Math.min(dp[i][k] + dp[k+1][j] + s[j] - s[i-1], dp[i][j]);
}
}
System.out.println(dp[1][N]);
}
}四、计数类DP
4.1 整数划分
一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。输入样例：
5
输出样例：
7
基本思考框架
// 方法一：类似完全背包问题
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
Scanner reader = new Scanner(System.in);
int M = (int) (1e9 + 7);
int n = reader.nextInt();
int[][] dp = new int[n+1][n+1];
for(int i=0; i<=n; i++)
dp[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
for(int i=1; i<=n; i++){
for(int j=0; j<=n; j++){
dp[i][j] = dp[i-1][j]%M;
if(j >= i)
dp[i][j] = (dp[i-1][j] + dp[i][j-i])%M;
}
}
System.out.println(dp[n][n]);
}
}五、其他类型
5.1 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
class Solution {
public boolean isMatch(String _s, String _p) {
int n = _s.length();
int m = _p.length();
char[] s = _s.toCharArray();
char[] p = _p.toCharArray();
boolean[][] dp = new boolean[n + 1][m + 1];
//S为空，P为空时两个字符串相等
dp[0][0] = true;
//当字符串S为空，模式串P不空，检查P中是否有*
for(int j = 1; j <= m; ++j) {
if(p[j - 1] == '*') {
dp[0][j] = true;
} else {
break;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <=m; ++j) {
//如果P当前是 *，从递归的角度看
//可以将S的当前字符去掉(dp[i-1][j])
//也可以去掉P的当前字符(dp[i][j-1])
if(p[j - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
//否则，要看P和S的当前字符是否匹配，或者P当前字符为?
//如果当前字符匹配，从递归的角度看
//可以去掉S的当前字符，P的当前字符(dp[i-1][j-1])
else {
boolean isFirstMatch = p[j - 1] == s[i - 1] || p[j - 1] == '?';
dp[i][j] = isFirstMatch && dp[i - 1][j - 1];
}
}
}
return dp[n][m];
}
}5.2 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。输入：s = "aab" p = "cab"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
char[] chs = s.toCharArray();
char[] chp = p.toCharArray();
boolean[][] dp = new boolean[n+1][m+1];
dp[0][0] = true;
for(int i=1; i<=m; i++){
char ch = chp[i-1];
if(i>1){
if(ch == '*'){
dp[0][i] = dp[0][i-2];
}else{
dp[0][i] = false;
}
}else{
if(ch == '*')
dp[0][i] = true;
}
}
for(int i=1; i<=n; i++){
char ch1 = chs[i-1];
for(int j=1; j<=m; j++){
char ch2 = chp[j-1];
if(ch1 == ch2 || ch2 == '.')
dp[i][j] = dp[i-1][j-1];
else if(ch2 == '*'){
if(j > 1){
if(dp[i][j-2])
dp[i][j] = true; // * 前面的字符出现0次
else{
char prev = p.charAt(j-2);
if(prev == ch1 || prev == '.')
dp[i][j] = dp[i-1][j]; // * 前面的字符出现多次
}
}
}
}
}
return dp[n][m];
}
}5.3 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
思路：
- 明确「不选」第一间：
初始化 f[0][0]f[0][0] 和 f[0][1]f[0][1]，均为 00。
先从「第二间」开始递推到「倒数第二间」的最大价值。
再处理「最后一间」的情况：由于明确了「不选第一间」，则最后的最大价值为 max(f[n - 2][1], f[n - 2][0] + nums[n - 1])max(f[n−2][1],f[n−2][0]+nums[n−1])。
- 允许「选」第一间：
初始化 f[0][0]f[0][0] 和 f[0][1]f[0][1]，分别为 00 和 nums[0]nums[0]。
先从「第二间」开始递推到「倒数第二间」的最大价值。
再处理「最后一间」的情况：由于明确了「选第一间」，则最后的最大价值为 max(f[n - 2][0], f[n - 2][1])max(f[n−2][0],f[n−2][1])。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1)
return nums[0];
else if(n == 2){
return Math.max(nums[0], nums[1]);
}
return Math.max(process(nums, 0, n-2), process(nums, 1, n-1));
}
public int process(int[] nums, int left, int right){
int first = nums[left], second = Math.max(nums[left], nums[left+1]);
for(int i=left+2; i<=right; i++){
int tmp = second;
second = Math.max(first+nums[i], second);
first = tmp;
}
return second;
}
}5.4 交错字符串
思路：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length())
return false;
int m = s1.length(), n = s2.length();
System.out.println(m +"..." +n);
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int i=0; i<=m; i++){
for(int j=0; j<=n; j++){
if(i > 0)
dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1));
if(j > 0)
dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
}
}
return dp[m][n];
}
}
查看15道真题和解析