hdu1159 lcs模板题

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
const int maxn = 250;
char X[maxn], Y[maxn];
int main() {
    while (scanf("%s%s", X, Y) == 2) {
        int dp[maxn][maxn];
        memset(dp, 0, sizeof(dp));
        int n1 = strlen(X); int n2 = strlen(Y);
        for(int i=1;i<=n1;++i)
            for (int j = 1; j <= n2; ++j) {
                if (X[i - 1] == Y[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        printf("%d\n", dp[n1][n2]);
    }
    
}

一道lcs的模板题目,试着用递推的方法去写不是tl就是wa很奇怪，看不出来问题

数组下标有一个偏移，应该是从0开始，而不是从1开始。所以应该把i和j的循环改为从0开始，同时在数组访问时应该访问i-1和j-1的位置。

另外，在计算dp[i][j]时，需要分别考虑当前字符匹配和不匹配的情况，可以使用三目运算符或者if-else语句进行判断，这样可以使代码更加清晰易懂。

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 250;
char X[maxn], Y[maxn];
int dp[maxn][maxn];
int main() {
    while (scanf("%s%s", X, Y) == 2) {
        memset(dp, 0, sizeof(dp));
        int n1 = strlen(X); int n2 = strlen(Y);
        for(int i=0;i<n1;++i)
            for (int j = 0; j < n2; ++j) {
                if (X[i] == Y[j])dp[i+1][j+1] = dp[i][j] + 1;
                else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        printf("%d\n", dp[n1][n2]);
    }
    return 0;
}