算法模板--动态规划

DP动态规划（输入分解问题，关注子树）

• 假设dp[0,...,i-1]被计算出来了，考虑怎么求dp[i]

• 遍历过程中，所需的状态必须是已经被计算出来

• 两个字符串的DP，一般用两个指针指向最后，再往前移动，缩小问题规模

需要明确：

    // 定义dp[i]：
    // base case:
    // 状态：
    // 选择：
    // 转移方程：

# 自顶向下递归的动态规划
# 可以利用备忘录
# dp体现在函数参数
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# dp体现在数组索引
# 初始化 base case
dp[0][0][...] = base case # DP table
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for 选择 in 所有可能的选择:
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)