# 动态规划(Dynamic Programming)

1. 递归+记忆化 —> 递推
2. 状态的定义:opt[n], dp[n], fib[n]
3. 状态转移⽅方程:opt[n] = best_of(opt[n-1], opt[n-2], ...) 4. 最优⼦子结构

# 斐波那契数列列

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

递推公式:F[n] = F[n-1] + F[n-2]

int fib(int n) {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2)
}

# 递归 + 记忆化 ==> 递推

递推公式: F[n] = F[n - 1] + F[n -2]

F[0] = 0,  F[1] = 1
for (int i = 2; i <= n; ++i) {
    F[i] = F[i - 1] + F[i - 2]
}

# 动态规划 vs 回溯 vs 贪⼼心算法

• 回溯(递归)— 重复计算
• 贪⼼算法 — 永远局部最优
• 动态规划 — 记录局部最优子结构 / 多种记录值

# 实战题⽬

1. https://leetcode.com/problems/climbing-stairs/description/
2. https://leetcode.com/problems/triangle/description/
3. https://leetcode.com/problems/maximum-product-subarray/description/
4. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/#/description
5. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
6. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
7. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
8. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
9. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
10. https://leetcode.com/problems/longest-increasing-subsequence
11. https://leetcode.com/problems/coin-change/ 12.https://leetcode.com/problems/edit-distance/