【C/C++】最长公共子序列（LCS）/动态规划

晴神这个的最巧妙之处，在于用dp[i][0] = dp[0][j] = 0的边界条件

这样从1的下标开始填数组的时候，递推公式dp[i-1][j-1]之类的不会报错

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

   string str1, str2;

   cin >> str1 >> str2;

   int len1 = str1.length(); //i

   int len2 = str2.length(); //j

   vector<vector<int>> dp;

   //根据长度开创一个动态二维数组

   //vector的初始化，先全部置零

   vector<int> tmp;

   tmp.insert(tmp.begin(), len2 + 1, 0);

   dp.insert(dp.begin(), len1 + 1, tmp);

   //填写第一个

   if (str1[0] == str2[0])

   {

      dp[0][0] = 1;

   }

   //写状态转移方程

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

   {

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

      {

         if(str1[i-1] == str2[j-1])

         {

            dp[i][j] = dp[i-1][j-1] + 1;

         }

         else

         {

            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

         }

      }

   }

   cout << dp[len1][len2] << endl; //数组下标从0开始，直接输出相当于+1了。

   system("pause");

}

巴特西

【C/C++】最长公共子序列（LCS）/动态规划

最新文章

热门文章