一、动态规划（DP）简介
动态规划（Dynamic Programming，简称DP）是运筹学的一个分支，它是一种通过将复杂问题分解成多个重叠的子问题，并通过子问题的解来构建整个问题的解的算法。在动态规划中，有几个核心概念需要理解：
- 状态：状态通常表示为形如dp[i][j] = val的取值，其中i和j是用于描述和确定状态所需的变量（下标），而val则是该状态对应的值。
- 状态转移：状态转移描述了不同状态之间如何相互转化。这通常可以表示为一个数学表达式，而转移的方向则决定了算法是迭代还是递归地进行。
- 最终状态：最终状态即题目所要求解的状态，也是我们通过动态规划算法最终要得到的答案。
动态规划的关键在于找到子问题之间的重叠关系，并存储这些子问题的解以避免重复计算。通过这种方式，动态规划能够在多项式时间内解决一些看似复杂的问题，如背包问题、最短路径问题等。在实际应用中，动态规划被广泛用于优化和控制问题，以及计算机视觉、生物信息学等领域。
二、动态规划的解题步骤
步骤一：确定状态
首先，需要明确问题的状态表示。在动态规划问题中，状态通常定义为“到第i个为止，xx为j（xx为k）的方案数/最小代价/最大价值”等。这里，“i”、“j”和可能的“k”是状态的参数，它们根据具体问题而定。状态的确切定义取决于问题的性质和所需优化的目标（如最小代价、最大价值或方案数）。
步骤二：确定状态转移方程
状态转移方程是动态规划的核心，确定状态转移方程，即从已知状态得到新状态的方法，并确保按照这个方向一定可以正确地得到最终状态。根据状态转移的方向来决定使用迭代法还是递归法（记忆化）。状态转移方程的确立通常基于问题的特定条件和约束。
步骤三：确定最终状态并输出
最终状态通常是问题的解所对应的状态。在确定了状态转移方程后，我们需要按照这个方程迭代或递归地计算出所有可能的状态，直到达到最终状态。最终状态可能是通过迭代法逐步累积得到，也可能是通过递归法（结合记忆化以避免重复计算）逐步回溯得到。一旦到达最终状态，我们就可以根据问题的要求输出相应的解，如最小代价、最大价值或特定条件下的方案数。
综上所述，这三个步骤——确定状态、确定状态转移方程和确定最终状态并输出——构成了动态规划求解问题的一般框架。在实际应用中，根据具体问题的不同，这些步骤的具体实现方式也会有所不同。
三、线性DP例题
（一）数字三角形（最大路径）
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。
输入描述
输入的第一行包含一个整数 N(1 ≤ N
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。
输出描述
输出一个整数，表示答案。
输入样例
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例
30
思路：
- 从最后一层向上，取最大值累加。
- 确定状态：设状态dp[ i ][ j ] = a[ i ][ j ] + max(dp[ i + 1 ][ j ], dp[ i + 1 ][ j + 1 ])；
- 状态转移方程为dp[i][j]=max(dp[i+1]lj]，dp[i +1][j + 1]) ；
- 因为这里需要用下面的状态更新上面的，所以我们应该从下往上进行状态转移。最后输出dp[1][1]
#include using namespace std; using ll = long long; const int N = 105; ll a[N][N], dp[N][N]; int main() { int n; cin >> n; for (int i = 1; i a[i][j]; for (int i = n; i >= 1; i--) for (int j = 1; j > m; vectordp(n + 1, 1);int temp = 0; for (int i = 1; i > temp; dp[temp] = 0; } for (int i = 2; i > k; dp[0] = prefix[0] = 1;// 初始化dp和prefix数组的第0项为1，表示空序列的方案数为1 for (int i = 1; i
还没有评论，来说两句吧...