跳转至

DP (Dynamic Programming)

动态规划将问题分解为**重叠子问题**，利用记忆化或递推避免重复计算。

核心思路：定义状态 → 写出状态转移方程 → 确定边界条件。

经典问题

斐波那契数列

C++
int fibonaci(int i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonaci(i - 1) + fibonaci(i - 2);
}

Source: dsa/alg/permutation_combination.cpp

饼干分配问题

问题1：n 块饼，每天吃 1~3 块，吃完为止，共有多少种吃法？

状态转移：f(n) = f(n-1) + f(n-2) + f(n-3)，边界：f(0)=1

C++
int f1(int n) {
    if (n <= 0) return n == 0;
    return f1(n-1) + f1(n-2) + f1(n-3);
}
// f1(10) = 274

问题2：n 块饼干分 t 天吃完，每天吃 1 或 2 块，共有多少种吃法？

C++
int f2(int n, int t) {
    if (n > 2*t || n < t) return 0;
    if (t == 1) return 1;
    return f2(n-1, t-1) + f2(n-2, t-1);
}
// f2(10, 7) = 35

LeetCode