Python 中自底向上的动态规划算法

自底向上的动态规划算法是一种递推的算法，它从最简单的问题开始逐步求解更复杂的问题。在实现上，我们需要定义状态和状态转移方程。

例如，我们可以考虑一个经典的动态规划问题——最长公共子序列（LCS）。给定两个字符串S1和S2，求它们的最长公共子序列的长度。

定义状态：我们用dp[i][j]表示S1[0:i]和S2[0:j]的最长公共子序列的长度。其中，i和j的取值范围为[0, len(S1)]和[0, len(S2)]。

状态转移方程：如果S1[i-1]等于S2[j-1]，那么dp[i][j]就是dp[i-1][j-1]+1。如果S1[i-1]不等于S2[j-1]，那么dp[i][j]就是dp[i-1][j]和dp[i][j-1]的较大值。

以下是Python代码演示：

def longestCommonSubsequence(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[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[m][n]

当我们要求解dp[m][n]时，所有的dp[i][j]都已经被计算出来了。最终的结果就是dp[m][n]。

在上述代码中，我们首先定义了dp数组，然后使用双重循环遍历所有的状态。最后返回dp[m][n]即可。