最长的公共子序列和背包是DP中最简单的问题，但有助于研究一些事情
为了整理DP，整理如下。 (包括滚动数组) )。
1 )最长公共子序列长度的动态规划方程
有字符串a[0.n]、b[0.m]。 接下来是递归公式。 字符串a对应于二维阵列num的行，字符串b对应于二维阵列num的列。
此外，用二维排列flag记录下标i和j的方向。 数字"1"表示斜下方； 数字"2"表示水平为右； 数字“3”表示纵向向下。 这样便于以后求解最长的公共子序列。
# include bits/stdc.husingnamespacestd； char a[500]，b[500]； char num[501][501]； //记录中间结果的序列char flag[501][501]； //用于标识下标流的令牌数组。 公共子序列void LCS ()//动态规划求解(for(inti=1； I=Strlen(a )； I ) for(intj=1； j=Strlen(b； j () if ) a[i-1]==b[j-1] ) /此处下标为I-1和j-1num[I](j )=num[I-1][j-1]1、flag[I] ) j ) else num[i][j]=num[i-1][j]，flag[i][j]=3； ///向下标记}(voidgetLCS ) ) )//)反推方式求最长公共子序列) { char res[500]，pnt=0； ///pnt用于保存结果的数组标志位for(intI=strlen(a )，j=strlen(b ) b )； i0j0； (if ) flag[I][j]==1) res[pnt ]=a[i-1]、I--、j--； //斜下方为elseif(flag[I][j]==2) j----； //斜右标记elseif(flag[I][j]==3) I----； //斜下方标记时(for ) I=pnt-1； i=0； I--； printf('%c”，res[i]； (}int main ) ) { int i； strcpy(a，' ABCBDAB '； strcpy(b，' BDCABA ' )； memset(num，0，sizeof ) num )； memset(flag，0，sizeof ) flag )； LCS (； printf('%dn '，num[strlen(a ) ][strlen(b ) b ) ]； getLCS (； 返回0； }
滚动数组，变得简洁了
滚动排列将n*m的二维排列压缩为2*m的排列，只使用now层和pre层的数据(这一层和前一层)，反复进行now和pre的交换，实现n*m的排列功能，大大优化了空间复杂度。
虽然也有可以一维实现的方法，但是代码很难理解，所以我个人认为没有这个必要(代码美丽是王道)。
# include bits/stdc.husingnamespacestd； int main () ) { int i，j，dp[2][10086]，t； char a[10086]，b[10086]； bool now，pre； scanf('%d '，t )； wile(t-- ) Scanf ) ' %s%s '，a，b )； memset(DP，0，sizeof ) DP )； intLena=strlen(a )，lenb=strlen(b ) ) b； for(now=1，pre=0，i=0； ilena； I ) for(swap ) now，pre ) j=0； jlenb； j ) if(a ) I )==b ) j ) ) dp[now][j 1]=dp[pre][j] 1； else DP [ now ] [ J1 ]=DP [ pre ] [ J1 ] DP [ now ] [ j ]？ dp[pre][j 1]:dp[now][j]； printf(%d(n )，dp[now][lenb]； } return 0； }