动态规划

2024-07-14 09:03| 来源: 网络整理| 查看: 265

能用动规解决的问题的特点 1) 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。 2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。思考动态规划的第一点：最优子结构：子问题最优时母问题通过选择后一定最优的情况叫做最优子结构。思考动态规划的第二点：子问题重叠：我们把母问题和子问题本质上是同一个问题的情况，称为子问题重叠。然而问题中出现的不同点往往就是被子问题之间传递的参数。思考动态规划的第三点：边界：我们把这种子问题在一定时候就不再需要提出子子问题的情况叫做边界，没有边界就会出现死循环。思考动态规划的第四点：

子问题独立：我们把折后总一个母问题在对子问题选择时，当前被选择的子问题两两互不影响叫做“子问题独立”。