在我们写题中,总会遇到深搜和广搜超时的情况,这样就需要一个新的算法来帮助我们,那就是——动态规划
目录
动态规划介绍
动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。
动态规划,英文是Dynamic Programming,简称DP,擅长解决“多阶段 决策问题”,利用各个阶段的递推关系,逐个确定每个阶段的最优决策,并最终得到原问题的最优决
例题
蒜头君要回家,已知蒜头君在 (1,1) 位置,家在 (n,n) 坐标处。蒜头君走到一个点 (i,j) 会花费一定的体力 aij ,而且蒜头君只会往家的方向走,也就是只能往上,或者往右走。蒜头君想知道:他 回家需要花费的最少体力 是多少。
例如下表所示,格子中的数字代表走到该格子花费的体力:
对于该表来说,共花费体力为:3+2+4+3=12。
5 | 4 | 3(家) |
6 | 2 | 5 |
蒜头君 | 3 | 4 |
我们把走到一个点看做一个状态,走到一个点只有两种方式 ,一个是 从下面走到该点 ,
一种是 从左边走到该点 。那么点 (i,j) 要么是从 (i−1,j) 走到 (i,j),要么是从点 (i,j−1) 走到所以从哪个点走
到 (i,j) 就是一个决策,我们用 dp(i,j) 来代表走到点 (i,j) 一共花费的最少体力。
我们需要花费最少力气走到家,所以可以得到状态转移方程:
dp(i,j)=min( dp(i−1,j) , dp(i,j−1) )+ a ij
根据转移方程我们可以推出走到每个点花费的最少体力。
可以看出来,动态规划算法的核心是DP方程。
所以说,状态转换方程(DP方程)就是算法的核心,那么设计DP方程,要有什么注意的呢?以下列出来几点!
1、最优化子问题
从上面的算法三要素中,可以看出,dp方程是最优子问题中归纳而来的。什么才 是“最优子题”呢?不管之前决策是否是最优决策,都必须保证从现在开始的 决策是在之前的基础上最优。具体说我们默认dp1和dp2就是最优的,在此基 础上,得到最优的dp3。
2、不影响后续决策
由于上一条我们看到,如果dp1的决策会影响到dp2和dp3的决策,那么dp3 = dp2+dp1就不成了,所以,要一定保证,每个阶段的决策仅受之前决策的影响,但不影响之后阶段的决策
点赞+关注!
相关作品:mjyleon的博客系列作品