1265：【例9.9】最长公共子序列 动态规划
题目链接
题目：
思路
最长-最值问题、重叠子问题、最优结构-前面序列的公共序列最优值是后续序列的子问题、无后效性也满足
-
确定状态、变量：序列是没有要求要连续，因此只能用长度为i的串a分别和长度为（1-j）串b去找最值，因此需要二维数组dp[i] [j]去处理串a长度i，串2长度j时对应的最大字串的长度
-
确定选择/方程
-
因为要用到前一个dp的值，所以初始化需要在数据之前预留一个dp[0] [j] =0 和dp[i] [0] =0 作边界，所以数据从dp[1] [] dp[] [1] 开始生效。但注意我们字符串是从下标0开始
-
如果当前两个字符相等，dp[i] [j] = dp[i-1] [j-1] +1 ，如果不等，就判断长度为i-1串a&长度j的串b 和 长度为j-1串b&长度i的串a的最长子序列谁长就行
-
当a[i-1] = b[i-1] 时
dp[i] [j] = dp[i-1] [j-1] +1, 当a[i-1] != b [i-1] 时,dp[i] [j] = max(dp[i] [j-1] , dp[i-1] [j])
-
-
确认边界：由于要判断上一个和左边一个，所以可以先设置初始值0(直接定义全局变量即可)
数据范围
代码参考
#include <bits/stdc++.h>
#define MAXN 1005
using namespace std;
int dp[MAXN][MAXN] ;//均初始化为0
int main(){string a,b; // cin>>a>>b;int l1 = a.size(),l2 = b.size();//处理边界-全局变量默认值为1 不做处理 for(int i=1;i<=l2;i++){ //a作行，b作列 dp数组中加了第一行第一列都为0 所以dp是l2行 l1列 for(int j=1;j<=l1;j++){ //长度为1 则无法处理 if(b[i-1] == a[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}
// cout<<dp[i][j]<<" ";}
// cout<<endl;}cout<<dp[l2][l1];return 0;
}