---
title: "线性dp求具体方案"
created: 2025-11-28
tags:
  - 算法
---

# 线性dp求具体方案

线性dp中的 求最长上升子序列 我们很容易求出 是多长 或者 和最大为多少

但具体是选择了哪些呢 发现突然一问还是有点懵

回溯路径这里复习一下

最长上升子序列 因为选择不外乎就是前面的某个和现在进行比较

所以可以在更新的时候记录从哪里转移而来 然后使用回溯路径的方式（pre）实现路径输出

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1010;
int a[N];
int f[N];//考虑到第i个数 以i结尾的最长上升子序列的所有情况 属性max
int n;

int g[N];//记录路径

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		f[i]=1;
		g[i]=0;//0 表示只有一个数
		for(int j=1;j<i;j++){
			if(a[j]<a[i]) //f[i]=max(f[i],f[j]+1);
			{
			    if(f[j]+1 > f[i]){
			        f[i]=f[j]+1;
			        g[i]=j;//记录从j转移到i
			    }
			}
		}
	}
	int res=0;
	int k=0;//记录最大值的下标
	for(int i=1;i<=n;i++){
		res=max(res,f[i]);
		if(f[i]>f[k])
		    k=i;
	}
	cout<<res<<endl;

	//此时 k为最大值的下标 最长的长度为f[k]
	//又有g[]一路记录某点是由哪个点转移而来 自然可以倒推
	//当然这样得到的是逆序的 可以存在数组中 reverse一下
	vector<int> ans;
	for(int i=0,len=f[k];i<len;i++){
	    ans.push_back(a[k]);
	    k=g[k];
	}
	reverse(ans.begin(),ans.end());
	for(auto x:ans) cout<<x<<" ";
	return 0;
 }
```

最长公共子序列

选择比较多 要考虑 A中第i个在不在里面 B中第j个在不在里面 不方便记录到底从哪里转移而来

这里选择和背包回溯一样的方法 倒着再做一遍 如果有相等就选择（贪心思想） 可能不是唯一解 但一定是一个解

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N = 1010;

int n, m;

char a[N], b[N];

int f[N][N];

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin >> n >> m;

    cin >> a + 1 >> b + 1;

    for (int i = 1; i <= n; i ++){

        for (int j = 1; j <= m; j ++){

            f[i][j] = max(f[i - 1][j], f[i][j - 1]);

            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);

        }

    }

    cout << f[n][m] << endl;

    string res;

    // 一个倒序的过程

    for (int i = n, j = m; i && j; )

    {

        if (a[i] == b[j]) 	res += a[i], i --, j --;

        else if (f[i - 1][j] > f[i][j - 1]) 	i --;

        else 	j --;

    }

    reverse(res.begin(), res.end());

    cout << res << endl;

	return 0;

}
```

这里再挂一下[[游园安排|游园安排]]的重写代码
虽然还是不能ac

```typescript
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

vector<string> words;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	string og; cin>>og;

	string tmp;

	for(int i=0;i<og.size();i++){

		if(isupper(og[i])){

			if(!tmp.empty()){

				words.push_back(tmp);

			}

			tmp=og[i];

		}

		else

			tmp+=og[i];

	}

	if(!tmp.empty())

		words.push_back(tmp);

	vector<string> copy(words);

	sort(words.begin(),words.end());

	copy.insert(copy.begin()," ");

	words.insert(words.begin()," ");

	//lcs

	int n=copy.size()-1,m=words.size()-1;

	vector<vector<int>> f(n+1,vector<int>(m+1,0));

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(copy[i]==words[j])

				f[i][j]=f[i-1][j-1]+1;

			else

				f[i][j]=max({f[i-1][j-1],f[i-1][j],f[i][j-1]});

		}

	}

	//回溯

	vector<string> res;

	for(int i=n,j=m;i&&j;){

		if(copy[i]==words[j]){

			res.push_back(copy[i]);

			i--;

			j--;

		}

		else if(f[i-1][j]>f[i][j-1])

			i--;

		else

			j--;

	}

	reverse(res.begin(),res.end());

	for(auto x:res){

		cout<<x;

	}

	return 0;

}
```

---
⬅️ [[动态规划|动态规划]] 🏠 [[00-冲刺国赛]] ➡️ [[线性dp遗留问题|线性dp遗留问题]]