最长公共子序列java-用动态规划法最长公共子序列

1. dp 数组的定义

下标： 以 i - 1 和 j - 1 为结尾的子序列

值：以 i - 1 和 j - 1 为结尾的最长公共子序列的长度

2. 递推公式

if(text1[i - 1] == text2[j - 1])     // 相等        
    dp[i][j] = dp[i - 1][j - 1] + 1 ;
else
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 

不相等分为两种情况

i - 1 之后，再与当前的 j 比较

例如：abcd abe，此时的 c 和 e 不相等，所以就向前比较，ab 与 abe

|i| |j|

j - 1 之后最长公共子序列java，再与当前的 i 比较

例如：abcd abe，此时的 c 和 e 不相等，所以就向前比较，abc 与 ab

3. 初始化，因为是从 dp数组的定义是从 i - 1 和 j - 1 进行比较的最长公共子序列java，所以可以默认初始化

4. 遍历顺序

从小到大

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector> dp(text1.size()+ 1, vector(text2.size() + 1, 0));
        int res = 0;
        for(int i = 1 ; i <= text1.size() ; i++)  // 这里是 <= 
        {
            for(int j = 1 ; j <= text2.size(); j++) // 这里是 <= 
            {
                if(text1[i - 1] == text2[j - 1])                
                    dp[i][j] = dp[i - 1][j - 1] + 1 ;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
            }   
        }
        return dp[text1.size()][text2.size()];
    }
};