算法学习—— 动态规划 状态方程_动态规划的状态方程

一、最大连续子序列和：

dp[i] = max{ A[i] , dp[i-1] + A[i] };

边界：dp[0] = A[0];

 

二、最长不下降序列

dp[i] = max{1,dp[j] +1}    其中j = 1,2,3......i-1; 且有A[i]>A[j]；

边界：dp[i] = 1;

 

三 、最长公共子序列

有长度：str1 = n;     str2 = m;

设dp[n+1][m+1];

因此有：

dp[i][j] = dp[i-1][j-1] + 1    if str1[i] == str2[j]

dp[i][j] = max{ dp[i-1][j], dp[i][j-1]}     if str1[i] != str2[j]

边界 dp[0][i] = 0, dp[j][0] = 0;

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

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

 

四、最大回文串

dp[i][j] = dp[i+1][j-1] ,     if    S[i] == S[j]

dp[i][j] = 0,                     if    S[i] != S[j]

const int maxn = 1000;
char S[maxn];
int dp[maxn][maxn];
 
int main(){
    gets(S);
    int