加油努力不懈气|线性DP 加油努力不懈气|dp

线性DP #1.LIS问题（最长上升子序列） F[i]F [ i ] 表示以 A[i]A [ i ] 为结尾的“最长上升子序列”的长度
状态转移方程：
F[i]=max0<=j #2.LCS问题（最长公共子序列） F[i][j]F [ i ] [ j ] 表示前缀子串 A[1到i]A [ 1 到 i ] 与 B[1到j]B [ 1 到 j ] 的“最长公共子序列”的长度
状态转移方程：
F[i][j]=max(F[i?1][j]或F[i][j?1]或F[i?1][j?1]+1(ifA[i]=B[j]))F [ i ] [ j ] = m a x ( F [ i ? 1 ] [ j ] 或 F [ i ] [ j ? 1 ] 或 F [ i ? 1 ] [ j ? 1 ] + 1 ( i f A [ i ] = B [ j ] ) )
#3.数字三角形 F[i][j]F [ i ] [ j ] 表示从左上角走到第i行第j列，和最大是多少
状态转移方程：
F[i][j]=A[i][j]+max(F[i?1][j]或F[i?1][j?1](ifj>1))F [ i ] [ j ] = A [ i ] [ j ] + m a x ( F [ i ? 1 ] [ j ] 或 F [ i ? 1 ] [ j ? 1 ] ( i f j > 1 ) )
CODE

#include using namespace std; int n,a[1010][1010]; inline int read() { int num=0,flag=1; char c=getchar(); for (; c<'0'||c>'9'; c=getchar()) if (c=='-') flag=-1; for (; c>='0'&&c<='9'; c=getchar()) num=(num<<3)+(num<<1)+c-48; return num*flag; } void init() { n=read(); for (int i=1; i<=n; ++i) for (int j=1; j<=i; ++j) a[i][j]=read(); } void dp() { for (int i=n-1; i>=1; --i) for (int j=1; j<=i; ++j) a[i][j]+=max(a[i+1][j],a[i+1][j+1]); printf("%d\n",a[1][1]); } int main() { init(); dp(); return 0; }

#4.LCIS问题（最长公共上升子序列） 【加油努力不懈气|线性DP】 F[i][j]F [ i ] [ j ] 表示 A1到AjA 1 到 A j 与 B1到BjB 1 到 B j 可以构成的以 BjB j 为结尾的LCIS的长度
对于“决策集合中的元素只增多不减少”的情景，就可以维护一个变量来记录决策集合的当前消息，只需要两重循环即可求解。
CODE

for (int i=1; i<=n; ++i) { int val=0; //val是决策集合S(i,j)中f[i-1][k]的最大值 for (int j=1; j<=m; ++j) { //原来的k循环+判断+状态转移 if (a[i]==b[j]) f[i][j]=val+1; else f[i][j]=f[i-1][j]; if (b[j]max(val,f[i-1][j]); //j即将增大为j+1,检查j能否进入新的决策集合 } }