动态规划

算法思想

• 有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串等等等。这就是规律，因为动态规划本身就是运筹学里的一种求最值的算法。

• 关键是明确【状态】和【选择】，列出【状态转移方程】

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

  • 状态：变化的量 （也就是原问题和子问题中会变化的变量）

  • 选择：前后状态间的可选项 （也就是导致「状态」产生变化的行为）

  • 状态转移方程：

    • dp[状态1][状态2]… = dp[状态1(变化)][状态2]…(选择1) + dp[状态1(变化)][状态2]…(选择2) + ...

    • base case：dp[0][0] = … ...

算法框架

function dp(){ 
    // 创建dp table
    const dp = new Array(n+1).fill(new Array(m+1)...);

    // base case
    dp[0][…] = …

    // 填充dp table
    for(){
        for(){
            …
            dp[][] = ...
        }
    }

    return dp[m][n];
}

优化

• 状态压缩：如果当前状态只和前一次状态有关，则用两变量存这两次的状态即可