c++动态规划
动态规划的基本概念
动态规划通常用于优化解决以下类型的问题：
- 重叠子问题：问题可以分解为多个子问题，且这些子问题会被多次计算。
- 最优子结构：问题的最优解可以通过子问题的最优解来构建。
为了避免重复计算，动态规划会使用一个数组或表格存储已经计算过的子问题的解，从而实现“记忆化”效果，降低时间复杂度。
动态规划的实现步骤
动态规划的解题一般遵循以下步骤：
-
定义状态：设定一个状态表示。例如，对于一个求最短路径的问题，可以定义dp[i]表示到节点i的最短路径长度。
-
状态转移方程：找出当前状态与之前状态之间的关系。这是动态规划的核心。比如，假设dp[i]的值可以通过dp[i-1]和dp[i-2]计算得出，那么状态转移方程可以表示为：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。
-
初始化：根据题意初始化dp数组的值。例如，若dp[0]表示开始状态，它的值可以设为0或其他值。
-
计算并获取结果：依据状态转移方程逐步填充dp数组，最终的解通常会在dp[n]或dp[n-1]等位置得到。
经典例题讲解
- 斐波那契数列
求解第n项的斐波那契数。斐波那契数列的状态转移方程是：
[ dp[i] = dp[i-1] + dp[i-2] ]
其中dp[0] = 0，dp[1] = 1。
int fibonacci(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];
}