5 y0 J- _3 H% T2 ?1.最优子结构：问题的最优解可以通过其子问题的最优解来构造。换句话说，问题的全局最优解可以通过局部最优解组合而成。& t/ O/ }4 Y% I% b# u$ L2 X
2.重叠子问题：问题的解可能会多次重复计算相同的子问题。动态规划通过保存已解决的子问题的解来避免重复计算，从而提高效率。 / N% A C) n6 o& G- d' X % \+ {1 Y( ]9 e/ q- ?4 I动态规划通常包括以下步骤：" s! D! d, p [
1 e0 T: _. [. W# d3.确定状态：将原问题划分为子问题，并确定问题的状态，即描述问题的局部情况。 . z- J9 u, {5 c9 v p4.定义状态转移方程：根据问题的最优子结构性质，定义子问题之间的关系，即如何通过子问题的解来求解原问题。 / t6 ~8 ?0 E+ {4 ` F3 T5.初始化：对于基本情况（通常是问题规模较小或边界情况），给出解的初始值。( [4 m9 v5 L. g! n; h9 ~: G5 W
6.递推求解：利用状态转移方程，从较小的子问题逐步推导出较大规模的子问题的解，直至求解出原问题的解。 D3 J: K7 e3 E/ k6 X
7.计算最终解：根据求解过程中保存的子问题的解，得到原问题的解。2 _( X8 L# ?5 R
! X* | L1 k* G! e9 l动态规划广泛应用于解决各种优化问题，例如最短路径问题、背包问题、最长公共子序列问题等。它的时间复杂度通常为问题规模的多项式级别，因此在一些具有较大规模的问题上表现出色。, u b: ^6 F9 J8 e5 A
; T3 F3 H: N* S G% p& p6 b
; w4 U7 O, t! y3 V