动态规划解题套路框架

发表于 | 分类于   |   次阅读
字数统计: 106 | 阅读时长 ≈ 1分钟 
1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

tips:

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

通过「备忘录」或者「dp table」的方法来优化递归树

坚持原创技术分享，您的支持将鼓励我继续创作！