掌握C语言动态规划（从零开始的动态规划算法教程）

经典案例：斐波那契数列

斐波那契数列是最常用来讲解动态规划的例子。数列定义如下：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) （当 n ≥ 2）

如果我们用递归直接实现，会有很多重复计算。而使用动态规划，我们可以“记住”已经计算过的结果，避免重复工作。

递归版本（效率低）

int fib(int n) {    if (n <= 1) return n;    return fib(n - 1) + fib(n - 2);}

动态规划版本（自底向上）

int fib_dp(int n) {    if (n <= 1) return n;        int dp[n + 1];    dp[0] = 0;    dp[1] = 1;        for (int i = 2; i <= n; i++) {        dp[i] = dp[i - 1] + dp[i - 2];    }        return dp[n];}

可以看到，动态规划版本只用一次循环就完成了计算，时间复杂度从指数级 O(2ⁿ) 降到了线性 O(n)，这就是动态规划入门的巨大优势！

另一个经典问题：背包问题

0-1 背包问题是动态规划中的标志性问题。给定一组物品，每个物品有重量和价值，在限定总重量的前提下，如何选择物品使得总价值最大？

C语言实现（二维DP表）

#include <stdio.h>#include <string.h>#define MAX(a, b) ((a) > (b) ? (a) : (b))int knapsack(int W, int wt[], int val[], int n) {    int dp[n + 1][W + 1];        // 初始化    memset(dp, 0, sizeof(dp));        for (int i = 1; i <= n; i++) {        for (int w = 1; w <= W; w++) {            if (wt[i - 1] <= w) {                dp[i][w] = MAX(                    val[i - 1] + dp[i - 1][w - wt[i - 1]],                    dp[i - 1][w]                );            } else {                dp[i][w] = dp[i - 1][w];            }        }    }        return dp[n][W];}

这个例子展示了如何构建一个二维表格来记录子问题的解。这也是C语言算法实现中非常典型的动态规划写法。

学习建议

• 先理解问题是否具有“重叠子问题”和“最优子结构”。
• 尝试画出状态转移方程（即 dp[i] = ... 的形式）。
• 从小规模例子入手，手动模拟 DP 表格的填充过程。
• 多练习经典题目：最长公共子序列、最长递增子序列、硬币找零等。

总结

动态规划虽然一开始看起来有点难，但只要掌握了基本套路，你会发现它其实非常强大且实用。无论是面试还是实际编程，C语言动态规划都是程序员必须掌握的核心技能之一。希望这篇动态规划算法教程能帮助你迈出成功的第一步！

继续练习，你也能成为动态规划高手！