Python列表语法与动态规划LCS代码if分支逻辑详解

首先给出参考实现代码：

class Solution(object):
 
    def LCS(self, text1,text2 ):
        # 倒序遍历第一个字符串，从最后一个字符走到第一个字符
        for i in range(len(text1)-1,-1,-1):
            # 倒序遍历第二个字符串，同理
            for j in range(len(text2)-1,-1,-1):
                if text1[i]==text2[j]:
                    dp[i][j]=1+dp[i+1][j+1]
                else:
                    dp[i][j]=max(dp[i][j+1],dp[i+1][j])
        return dp[0][0]

这段代码用自底向上的动态规划思路实现，作用是求两个字符串的最长公共子序列长度。比如输入text1='abcde'、text2='ace'时，最终返回结果是3。

涉及的基础Python语法说明 #

• 二维列表访问：代码里的dp是提前初始化好的二维列表，可以直接把它当成一张行列组成的表格，dp[i][j]的逻辑很简单：先拿到二维列表里第i个位置存的子列表（对应表格第i行），再拿这个子列表里第j个位置存的值（对应这一行的第j列）。这里每个dp[i][j]存的实际含义是：text1从索引i开始到末尾的子串，和text2从索引j开始到末尾的子串，两者的最长公共子序列长度。
• 倒序遍历的range写法：range(len(text1)-1,-1,-1)三个参数分别是遍历起点、遍历终点（不包含这个值）、步长，这里就是从字符串最后一个字符的索引（长度减1）开始，每次往前挪1位，一直走到索引0为止，实现从后往前遍历整个字符串。
• 补充说明：这段代码省略了dp数组的初始化步骤，实际运行时要先建一个大小为(len(text1)+1)行 × (len(text2)+1)列的二维数组，所有值初始填0即可——多出来的最后一行、最后一列对应i或者j走到字符串末尾的情况，空串和任何字符串的最长公共子序列长度都是0，不需要额外计算。

核心判断分支逻辑拆解 #

if text1[i]==text2[j]:对应的就是动态规划的状态转移逻辑，分两种情况处理：

• 当两个串当前位置的字符相等时：说明这个字符肯定可以算进公共子序列里，那当前位置的LCS长度，就等于两个串都跳过这个匹配字符之后，剩下的后缀子串的LCS长度再加1（算上当前匹配的这个字符），对应代码dp[i][j]=1+dp[i+1][j+1]。比如text1[i]和text2[j]都是'c'，那这俩匹配上了，剩下的text1[i+1:]和text2[j+1:]的LCS长度加1，就是当前位置的结果。
• 当两个串当前位置的字符不相等时：说明当前位置没法凑出公共字符，这时候有两种选择：要么跳过text1的当前字符，取text1[i+1:]和text2[j:]的LCS长度；要么跳过text2的当前字符，取text1[i:]和text2[j+1:]的LCS长度，两个结果里更大的那个就是当前位置的最优解，对应代码dp[i][j]=max(dp[i][j+1],dp[i+1][j])。

因为是从后往前遍历，计算dp[i][j]的时候，它依赖的dp[i+1][j+1]、dp[i][j+1]、dp[i+1][j]这三个位置的值都已经提前算好了，可以直接取值计算，等遍历到i=0、j=0的时候，对应的就是两个完整字符串的LCS长度，直接返回即可。

内容的提问来源于stack exchange，提问作者novicesnail