必读系列 3动态规划解题套路框架

说明

• 动态规划问题 一般是求最值问题
• 三要素: 重叠子问题、最优子结构、状态转移方程
• 状态转移方程 框架
  • 明确 状态转移方程 —> 定义dp数组/函数的含义 —-> 明确选择 —-> 明确 base case

斐波那契数列

暴力求解

int fib(int N) {
    if(N == 1 || N == 2) {
        return 1;
    }
    return fib(N - 1) + fib(N - 2);
}

• 存在大量重叠子问题

凑零钱问题

k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。

明确状态：原问题和子问题中变化的量。总金额amout。
确定dp函数的定义：当前的目标金额是n，至少需要dp(n)个硬币凑出。
确定选择并择优：可以做出什么选择改变状态。
确定base case：dp[0] = 0