企业官网建设流程全解析

一、什么是动态规划？

动态规划（Dynamic Programming, DP）是一种解决多阶段决策问题的算法思想。它通过把原问题分解为重叠的子问题，并保存子问题的解，避免大量重复计算，从而将指数级的时间复杂度降为多项式级别。
适用场景：

问题可以分解成相互依赖的子问题
子问题会被多次重复计算
子问题的最优解能构成原问题的最优解（最优子结构）

二、核心概念

状态定义

用一个或多个变量描述当前所处的情形，通常用数组下标表示。
例如 dp[i] 表示“前 i 个物品的最大价值”，或 dp[i][j] 表示“字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度”。
状态转移方程

描述状态之间如何推导的数学表达式，是 DP 的核心。
比如 0-1 背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
初始条件 / 边界

最小的子问题的解，通常是 dp[0]、dp[0][0] 等。
计算顺序

确定按什么顺序填充 DP 表格，保证计算当前状态时，依赖的状态已经算过。

三、动态规划的一般解题步骤

分析问题是否有重叠子问题和最优子结构
定义状态：明确 dp[i] 或 dp[i][j] 代表什么
推导状态转移方程
初始化边界
确定遍历顺序，用代码实现
可能的空间优化（用滚动数组代替二维数组）

四、经典例题（C++ 代码）

斐波那契数列
问题：求第 n 项斐波那契数 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

#include<iostream>#include<vector>usingnamespacestd;longlongfib(intn){if(n<=1)returnn;vector<longlong>dp(n+1);dp[0]=0;dp[1]=1;for(inti=2;i<=n;++i){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}intmain(){cout<<fib(50)<<endl;return0;}

背包问题
问题：有 n 个物品，每个物品重量 w[i]，价值 v[i]，背包容量为 W，每种物品只能选 0 或 1 个，求最大总价值。

状态定义：dp[i][j] —— 前 i 个物品放入容量为 j 的背包的最大价值。

intknapsack(intW,vector<int>weight,vector<int>value){intn=weight.size();vector<vector<int>>dp(n+1,vector<int>(W+1,0));for(inti=1;i<=n;++i){intw=weight[i-1],v=value[i-1];for(intj=1;j<=W;++j){if(j<w)dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);}}returndp[n][W];}

五、总结

动态规划是一门需要大量练习才能熟练掌握的技艺。本质是 “以空间换时间”，通过数组（表格）记录子问题的解，避免重复运算。学习路线建议：

先用递归写暴力解，画出递归树，发现重叠子问题
改为记忆化搜索（自顶向下）
推导 DP 表（自底向上）