动态规划是个啥？
date
Jun 4, 2021
slug
dp
status
Published
tags
学习
summary
递推？搜索？动态规划？傻傻的分不清楚
type
Post
1.动态规划与分治
分治：为了解决一个大问题，把它分成两个或多个小问题，分别解决。如：汉诺塔、快速排序
动态规划：用一个数组记录所有已解决的子问题的答案，无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组
动态规划减少子问题的重复计算
动态规划在实现时可以用递推的手段实现
2.动态规划与递推
递推：模4最优路径问题，最优策略的子策略不一定最优
递推法借用了动态规划的思想解决了动态规划不能解决的问题
3.动态规划与搜索
动态规划能解决的问题，搜索也能解决
动态规划是自底向上的递推求解
搜索是自顶向下的递归求解（这里指深度优先搜索，宽度优先搜索类似）
动态规划算法在时间效率上优于搜索算法
搜索可以排除一些无效状态，还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多
记忆化算法保存求解状态的解，综合了搜索和动态规划的优点
动态规划的优点：
当每个阶段的状态变量个数不多于三个，而每一个允许决策聚合不太大时，每个问题可穷举，再动态规划
动态规划的设计步骤
1.划分阶段
2.选择状态
3.确定决策并写出状态转移方程
4.写出规划方程（包括边界条件）
我对最短行军路线的理解（可能不对...
宽度优先搜索：f(G) = min(f(F1) + F1, f(F2) +F2)，从前往后算出每个阶段每个状态的最短路径
动态规划：最优路径上每一个节点到终点的路径都是最优的，可以从后向前开始逐段求最优子路线