核心思想
很多动态规划题目要求返回的答案不是一个简单数值，而是一个具体的方案
1、利用动态规划表生成决策路径，本章节题目1、题目2、题目3
2、有时候需要增加额外的路径收集结构，本章节题目4
对这一类的题目来说，动态规划是最重要的，得到具体方案只是一个比较简单的处理技巧
例题
最长公共子序列其中一个结果
题目描述： 给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则输出-1。 输入描述：
输出包括两行，第一行代表字符串str1，第二行代表str2。(1≤length(str1),length(str2)≤5000)(1≤length(str1),length(str2)≤5000)
输出描述：
输出一行，代表他们最长公共子序列。如果公共子序列的长度为空，则输出-1。
示例1
输入：
1A2C3D4B56 B1D23CA45B6A
输出：
123456
说明：
"123456"和“12C4B6”都是最长公共子序列，任意输出一个。
备注：
时间复杂度O(n∗m)O(n∗m)，空间复杂度O(n∗m)O(n∗m)。(n,m分别表示两个字符串长度)
解题思路：
首先这个题是一个最长公共子序列的问题，最长公共子序列的解法dp在 动态规划02：从递归入手二维动态规划中的例题中有过
现在的题意是求出具体的最长公共子序列，这里我们需要先求解出其对应的dp表，按照dp表的从最末尾进行逆推
逆推的过程依据于我们求解dp表的过程。
在求解dp表的过程中，基础的转移为
if(text1[i-1]==text2[j-1]){
ans=f2(text1,text2,i-1,j-1,dp)+1;
}else{
ans=Math.max(f2(text1,text2,i-1,j,dp),f2(text1,text2,i,j-1,dp));
} 现在我们就要依据这个进行反推，具体流程就是
找当前格子的左边和上边的格子，谁大，我们就走到那个点去
判断当前点对应的字符是否相同，相同则加入结果集合中去
代码如下：
package main.java.class086;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_LCS
* @description: 最长公共子序列其中一个结果
* // 给定两个字符串str1和str2
* // 输出两个字符串的最长公共子序列
* // 如果最长公共子序列为空，则输出-1
* // 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8
* @author: zs宝
* @create: 2025-10-16 10:56
* @Version 1.0
**/public class Code01_LCS {
public static int MAXN=5001;
public static int[][]dp=new int[MAXN][MAXN];
public static int n,m,k;
public static char[]ans=new char[MAXN];
public static char[]str1;
public static char[]str2;
public static void main (String[] args) throws IOException {
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
str1=buffer.readLine().toCharArray();
str2=buffer.readLine().toCharArray();
n=str1.length;
m=str2.length;
lcs();
if(k==0){
out.print(-1);
}else{
for(int i=0;i<k;i++){
out.print(ans[i]);
}
out.println();
}
out.flush();
out.close();
buffer.close();
}
public static void lcs(){
//进行动态规划，计算得到最长公共子序列长度
dp();
k=dp[n][m];
if(k>0){
for(int len=k,i=n,j=m;len>0;){
if(str1[i-1]==str2[j-1]){
ans[--len]=str1[i-1];
i--;
j--;
}else{
if(dp[i-1][j]>=dp[i][j-1]){
i--;
}else{
j--;
}
}
}
}
}
//求解dp表
public static void dp(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str1[i-1]==str2[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]);
}
}
}
}
}2、最小的必要团队
题目描述： 作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
例如，团队
team = [0, 1, 3]表示掌握技能分别为people[0]，people[1]，和people[3]的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。
示例 1：
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] 输出：[0,2]
示例 2：
输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]] 输出：[1,2]
提示：
1 <= req_skills.length <= 161 <= req_skills[i].length <= 16req_skills[i]由小写英文字母组成req_skills中的所有字符串 互不相同1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j]由小写英文字母组成people[i]中的所有字符串 互不相同people[i]中的每个技能是req_skills中的技能题目数据保证「必要团队」一定存在
解题思路：
这个题的动态规划的递归思路其实和01背包很像，要当前人员，不要当前人员
且dp的定义为
dp[i][j]:从第i个人出发，当前凑到的技能状态为j,到凑齐所有技能最少需要几个人这个题的主要难点在于对每个人拥有技能的处理，选了多个人时，如何判定技能状态的变化以及是否拿到了所有需要的技能
这里我们的解决思路时利用位运算来表示技能的掌握状态
我们将所有需要的技能用hashmap编号，n个技能用n位来表示
对于员工拥有的技能，如果包含了需要的技能，则在对应位上置为1
后续的技能判定，多个员工间的技能组合都可以用位运算|来表示
技能完整状态也可以用位运算表示
代码如下
package main.java.class086;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_SmallestSufficientTeam
* @description: 最小的必要团队
* // 作为项目经理，你规划了一份需求的技能清单req_skills
* // 并打算从备选人员名单people中选出些人组成必要团队
* // 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表
* // 所谓必要团队，就是在这个团队中
* // 对于所需求的技能列表req_skills中列出的每项技能，团队中至少有一名成员已经掌握
* // 请你返回规模最小的必要团队，团队成员用人员编号表示
* // 你可以按 任意顺序 返回答案，题目数据保证答案存在
* // 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/
* @author: zs宝
* @create: 2025-10-17 08:41
* @Version 1.0
**/public class Code02_SmallestSufficientTeam {
class Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
int n=req_skills.length;
int m=people.size();
//首先将需要的技能转化为位信息，每个人员的技能用位运算来表示
Map<String,Integer> map=new HashMap<>();
for(int i=0;i<n;i++){
map.put(req_skills[i],i);
}
//存储每个人员的技能，用位运算表示
int[] arr=new int[m];
for(int i=0,status;i<m;i++){
status=0;
for(String skill:people.get(i)){
//如果当前技能是需要的，才设置status
if(map.containsKey(skill)){
status|=1<<(map.get(skill));
}
}
arr[i]=status;
}
//定义dp数组
//dp[i][j]:从第i个人出发，当前凑到的技能状态为j,到凑齐所有技能最少需要几个人
int[][]dp=new int[m][1<<n];
for(int i=0;i<m;i++){
Arrays.fill(dp[i],-1);
}
int size=f(arr,n,m,0,0,dp);
//接下来就是依据dp表得到具体的最小方案
int []ans=new int[size];
for(int i=0,status=0,k=0;status!=(1<<n)-1 && k<size;i++){
//status技能还没有凑齐时才算
if(i==m-1 || dp[i][status]!=dp[i+1][status]){
ans[k++]=i;
status|=arr[i];
}
}
return ans;
}
/**
从第i个人出发，当前凑到的技能状态为status,到凑齐所有技能最少需要几个人
n：需要的技能总数
m:总共可用人数
*/
public int f(int[]arr,int n,int m,int i,int status,int[][]dp){
if(status==((1<<n)-1)){
//已经凑齐了所有技能，不用再凑人了
return 0;
}
//技能还没有凑齐的时候
//人已经用光了
if(i==m){
//就是当前组合不可用，直接反回一个极大值
return Integer.MAX_VALUE;
}
if(dp[i][status]!=-1){
return dp[i][status];
}
//当不要第i个人进团队时，需要多少人
int p1=f(arr,n,m,i+1,status,dp);
//当需要第i个人进团队时，需要多少人
int p2=Integer.MAX_VALUE;
int next=f(arr,n,m,i+1,status|arr[i],dp);
if(next!=Integer.MAX_VALUE){
//有效时
p2=1+next;
}
int ans=Math.min(p1,p2);
dp[i][status]=ans;
return ans;
}
}
}3、最长递增子序列字典序最小的结果
题目描述： 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的） 输入描述： 输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr (1≤arri≤1e9)(1≤arri≤1e9)。 输出描述： 输出一行。代表你求出的最长的递增子序列。 示例1 输入： 9 2 1 5 3 6 4 8 9 7 输出： 1 3 4 8 9 示例2 输入： 5 1 2 8 6 4 输出： 1 2 4 说明： 其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4） 备注： 时间复杂度O(nlogn)O(nlogn)，空间复杂度O(n)O(n)。
解题思路：
这个题仍然需要先求出dp表
这个属于最长递增子序列一类的题，关于其求解的方式在 动态规划07：最长递增子序列问题与扩展有详细的过程
这里我们由于题意要求定义的dp与动态规划07：最长递增子序列问题与扩展的定义有所不同
我们这里dp[i]定义的是从i-最后位置的最长递增子序列长度
在求出dp表后，我们需要按照题目给的最小字典序定义以及最长递增子序列的递推方式填充最终答案
其实最关键的还是如何求解最长递增子序列的dp表
本次再次写最长递增子序列的模版代码时，还是有写错的地方
一是在求解dp的循环中将辅助数组ends写成了arr
二是在find！=-1时，忘记更新ends数组
同时在得到具体方案的过程中，还有一个小点需要注意，那就是在已知从i位置到最后的最长递增子序列长度dp[i]的情况下, 如何根据dp[i]找到其在ans数组的对应位置
代码如下：
package main.java.class086;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_LIS
* @description: 最长递增子序列字典序最小的结果
* // 给定数组arr，设长度为n
* // 输出arr的最长递增子序列
* // 如果有多个答案，请输出其中字典序最小的
* // 注意这道题的字典序设定（根据提交的结果推论的）：
* // 每个数字看作是单独的字符，比如120认为比36的字典序大
* // 保证从左到右每个数字尽量小
* // 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
* // 测试链接 : https://www.luogu.com.cn/problem/T386911
* @author: zs宝
* @create: 2025-10-17 09:44
* @Version 1.0
**/public class Code03_LIS {
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int MAXN=100001;
public static int[]dp=new int[MAXN];
public static int[]ends=new int[MAXN];
public static int[]arr=new int[MAXN];
public static int n;
public static void main(String[] args) throws IOException{
BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(buffer);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
while(in.nextToken()!=StreamTokenizer.TT_EOF){
n=(int)in.nval;
for(int i=0;i<n;i++){
in.nextToken();
arr[i]=(int)in.nval;
}
//计算dp数组
int size=compute();
int []ans=new int[size];
for(int i=0;i<size;i++){
ans[i]=Integer.MAX_VALUE;
}
for(int i=0;i<n;i++){
if(dp[i]==size || arr[i]>ans[size-dp[i]-1]){
ans[size-dp[i]]=arr[i];
}
}
for(int i=0;i<size-1;i++){
out.print(ans[i]+" ");
}
out.print(ans[size-1]);
}
out.flush();
out.close();
buffer.close();
}
public static int compute(){
int cnt=0;
for(int i=n-1,find;i>=0;i--){
find=binarySearch(cnt,i);
if(find==-1){
ends[cnt++]=arr[i];
dp[i]=cnt;
}else{
ends[find]=arr[i];
dp[i]=find+1;
}
}
return cnt;
}
public static int binarySearch(int cnt,int i){
int l=0;
int r=cnt-1;
int m;
int ans=-1;
while(l<=r){
m=(l+r)/2;
if(ends[m]<=arr[i]){
r=m-1;
ans=m;
}else{
l=m+1;
}
}
return ans;
}
}
}4、潜水的最大时间与方案
题目描述： 在猴王的帮助下，小 A 终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小 A 有 n 个潜水工具。由于他还要背重重的背包，所以他只能背 m 重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有 v 阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。
输入格式
三个数 m,v,n 如题目所说。
接下来 n 行，每行三个数 ai,bi,ci 分别表示所含的重力，阻力，能够支撑的时间。
输出格式
第一行一个数，表示最长的时间。
接下来一行，若干个数，表示所选的物品。
输入输出样例
输入 #1
100 100 3 50 60 289 40 10 116 50 50 106
输出 #1
405 1 2
说明/提示
对于 100% 的数据，1≤m,v≤200，1≤n≤100。
数据保证一定有方案。
若有多种方案，输出前面尽量小的方案。
解题思路：
这个题动态规划上就是一个多维01背包，其中多维指的是满足的条件有多个
每次递归，带上之前的递归路径即可，重点还是动态规划，dp表出来，路径表也就跟着出来了
代码如下
package main.java.class086;
import java.io.*;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_Diving
* @description: 潜水的最大时间与方案
* // 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c
* // 因为背包有限，所以只能背重量不超过m的工具
* // 因为力气有限，所以只能背阻力不超过v的工具
* // 希望能在水下停留的时间最久
* // 返回最久的停留时间和下标字典序最小的选择工具的方案
* // 注意这道题的字典序设定（根据提交的结果推论的）：
* // 下标方案整体构成的字符串保证字典序最小
* // 比如下标方案"1 120"比下标方案"1 2"字典序小
* // 测试链接 : https://www.luogu.com.cn/problem/P1759
* @author: zs宝
* @create: 2025-10-17 10:45
* @Version 1.0
**/public class Code04_Diving {
public static int MAXN = 101;
public static int MAXM = 201;
public static int m, v, n;
public static int[][] arr = new int[MAXN][3];
//严格找着位置的动态规划
public static int[][][] dp1 = new int[MAXN][MAXM][MAXM];
//存储对应dp位置的路径
public static String[][][] path1 = new String[MAXN][MAXM][MAXM];
//严格按照位置的动态规划+空间压缩
public static int[][] dp2 = new int[MAXM][MAXM];
//存储对应dp位置的路径
public static String[][] path2 = new String[MAXM][MAXM];
public static void build1() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= v; k++) {
dp1[i][j][k] = 0;
path1[i][j][k] = null;
}
}
}
}
public static void build2() {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= v; k++) {
dp2[j][k] = 0;
path2[j][k] = null;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(buffer);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
m = (int) in.nval;
in.nextToken();
v = (int) in.nval;
in.nextToken();
n = (int) in.nval;
for (int i = 1; i <= n; i++) {
in.nextToken();
arr[i][0] = (int) in.nval;
in.nextToken();
arr[i][1] = (int) in.nval;
in.nextToken();
arr[i][2] = (int) in.nval;
}
compute();
out.println(dp2[m][v]);
out.println(path2[m][v]);
}
out.flush();
out.close();
buffer.close();
}
public static void compute() {
build2();
f2();
}
//多维01背包问题
//会内存溢出
//严格按照位置的动态规划
public static void f1() {
String p2;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= v; k++) {
//不要第i个工具时
dp1[i][j][k] = dp1[i - 1][j][k];
path1[i][j][k] = path1[i - 1][j][k];
if (j >= arr[i][0] && k >= arr[i][1]) {
//考虑要第i个工具
//先处理要第i个工具时的路径
if (path1[i][j - arr[i][0]][k - arr[i][1]] == null) {
p2 = String.valueOf(i);
} else {
p2 = path1[i - 1][j - arr[i][0]][k - arr[i][1]] + " " + String.valueOf(i);
}
if (dp1[i][j][k] < dp1[i - 1][j - arr[i][0]][k - arr[i][1]] + arr[i][2]) {
dp1[i][j][k] = dp1[i - 1][j - arr[i][0]][k - arr[i][1]] + arr[i][2];
path1[i][j][k] = p2;
} else if (dp1[i][j][k] == dp1[i - 1][j - arr[i][0]][k - arr[i][1]] + arr[i][2]) {
if (p2.compareTo(path1[i][j][k]) < 0) {
path1[i][j][k] = p2;
}
}
}
}
}
}
}
//多维01背包问题
//会内存溢出
//严格按照位置的动态规划+空间压缩
public static void f2() {
String p2;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= arr[i][0]; j--) {
for (int k = v; k >= arr[i][1]; k--) {
//不要第i个工具时,就和之前的一样
//考虑要第i个工具时
//先处理要第i个工具时的路径
if (path2[j - arr[i][0]][k - arr[i][1]] == null) {
p2 = String.valueOf(i);
} else {
p2 = path2[j - arr[i][0]][k - arr[i][1]] + " " + String.valueOf(i);
}
if (dp2[j][k] < dp2[j - arr[i][0]][k - arr[i][1]] + arr[i][2]) {
dp2[j][k] = dp2[j - arr[i][0]][k - arr[i][1]] + arr[i][2];
path2[j][k] = p2;
} else if (dp2[j][k] == dp2[j - arr[i][0]][k - arr[i][1]] + arr[i][2]) {
if (p2.compareTo(path2[j][k]) < 0) {
path2[j][k] = p2;
}
}
}
}
}
}
}