第一章：经典动态规划：最长公共子序列

labuladong经典动态规划：最长公共子序列

1143. 最长公共子序列

（在dp数组中添加0行和0列可以包含text为空的情况，并且更便于状态转移）

1. dp数组的含义： 对于 text1[0..i-1] 和 text2[0..j-1]，dp[i][j]中保存当前位置的最长公共子序列的长度
2. 状态转移方程：若当前元素相等，则在之前状态下+1 （dp[i][j]=dp[i-1][j-1]+1）。 若不相等，则继承之前的最大值（dp[i][j]=max(dp[i-1][j],dp[i][j-1])）
3. base case : 第0行和第0列初始化为0 。（至少有一个为空字符时，不可能有公共子序列 （两个都为空时，公共子序列长度也为0））

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        if not (text1 and text2): return 0
        m=len(text1)
        n=len(text2)
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                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[-1][-1]