POJ 1458 Common Subsequence

問題文

DP強化週間。

stringが2つ与えられる。LCS長を求めよ。

dp[i + 1][j + 1]:=(文字列1のi番目までと文字列2のj番目までのLCS長)でDP。

以下ソース。

int dp[1001][1001];
int main(){
  string s, t;
  while(cin >> s >> t){
    memset(dp, 0, sizeof(dp));
    int N = s.length();
    int M = t.length();

    //DP
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(s[i] == t[j])
	  dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
	else{
	  dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
	}
      }
    }
    cout << dp[N][M] << endl;
  }
  return 0;
}

さすがにこれできなかったらどうしようかと思った( ﾞ'ωﾞ` )。
できたからいいけど。。
(最初ケチってdp[100][100]で出したらREもらったが)