[BOJ]9251路LCS c++

https://www.acmicpc.net/problem/9251

質問する 最長共通部分数列(LCS)の問題は、2つの数列が与えられたときに、すべての部分数列の中で最も長い数列を検索することです。 例えば、ACAYKPとCAPCAKのLCSがACAKになります。

入力します.
ACAYKP
CAPCAK
出力します.
4

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
  char str1[1001], str2[1001];
  int dp[1001][1001] = {0,};
  int len1, len2;
  scanf("%s", str1);
  scanf("%s", str2);

  len1 = strlen(str1);
  len2 = strlen(str2);

  for(int i = 0; i < len1; i++) {
    for(int j = 0; j < len2; j++) {
      if(str1[i] == str2[j])
        dp[i + 1][j + 1] = dp[i][j] + 1;
      else
        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }

  printf("%d\n", dp[len1][len2]);
}

二つの状況に分けられる.
1.2つの文字列の現在の文字が一致する場合
2.2つの文字列の現在の文字が一致しない場合
1つ目の場合、2つの文字列から前の文字が見えると、求めた答えに1が加算され、2つ目の場合、前に求めた値に大きな値が加算されます.詳細については、次の例を参照してください.
例えば、ABC AABCがあります.
-0ABC00000A0111A0111B0122C0123
1つ目は文字列ABCとAABCの3です.ABとAABを比較すると、LCSの長さは2で、現在一致している文字「C」を加えると2になります.
2つ目のケースは文字列ABCとAABの2です.CとBは一致せず,CとBをそれぞれLCSに組み入れた.Cを含むABCとAAのLCSは1であり、Bを含むABとAABのLCSの長さは2である.したがって、ABCおよびAABのLCSの長さは、より大きな値2である.
dpを解くのに要する時間のうち、90%は考えているのではないでしょうか.他の人が作る点火式を見ると「あれはどう思う」と思うのですが、点火式は本当にいろいろあります.そのような考えが私の頭の中に出てきたらどんなにいいか、その前に探してみるのもいい勉強方法だと思います.見て、熟知して、時間が流れた後に、自分の力で解いてみます.dp万事通となる道は多くの問題に触れ、様々な問題に触れ、視野を広げる道です.💪🏻