【算法】动态规划

  • 时间:
  • 来源:互联网

1.解决什么类型问题

1.1 计数问题

如最典型的青蛙跳,也就是斐波那契数列、棋盘路径问题、

还有组合公式,不重复组合( Combination ),c(n, m)从n个选手中选出m个出道~(101哈哈哈哈哈),有多少种可能性?这个问题可以分解为两个子问题,根据最后一个人能不能进组合有两种可能:

最后一个人出道,剩余席位是m-1, 子问题是c(n-1, m-1)

最后一个人不能出道,剩余席位还是m,子问题是c(n-1,m)

c(n, m) =
 { c(n-1, m-1) + c(n-1, m)  , if n > 1 and m > 1 and n >= m
 { n                        , if m = 1
 { 1                        , if n = 1

这一类问题通常递推公式子问题的和,c(n, m) =c(n-1, m-1) + c(n-1, m)边界就是m=1或者n=1。

1.2 极值问题

背包问题,就是多阶段最优决策。一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条决策路径。
    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

棋盘最大和(最小和),从(0,0) 到 (n-1,n-1)路上数值最大和

这一类问题通常递推公式是子问题max、min值,如上题c[i][j] = max(c[i-1][j], c[i][j-1])  +  a[i][j];

还有最长递增子序列、最少找零问题、最大子数组等等,更多问题和详情可见top15动态规划

2.特性

2.1 重复子问题

如下图所示,求解斐波那契数列时,同一个子问题(图中划圈)的解重复求解,会导致组合爆炸,重复计算,为了解决这个问题,可以通过记忆化memoization解决,即记录子问题的解

 

2.2 无后效性

下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前的状态是对以往决策的总结,

棋盘最大和问题,如果当前状态是处于dp[i][j]上,下一时刻的状态就是dp[i+1][j],和dp[i][j+1],这两个状态仅和当前状态(到【i,j】的最大值)有关,对于dp[i-1][j-1]这些之前的状态不关心。

2.3 最优化子结构

假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的。

过程步骤

反复读取数据、计算数据、存储数据。实现方式有两种:递归循环迭代

1. 把原问题递归分割成多个更小的問題。(recurrence递归 分治)
   1-1. 子問題與原問題的求解方式皆類似。(optimal sub-structure最优子结构)
   1-2. 子問題會一而再、再而三的出現。(overlapping sub-problems重复子问题)
2. 设计计算过程:
   2-1. 确认每个问题有哪些子问题。(recurrence 递归)
   2-2. 确认总共有哪些问题。(state space 状态空间)
   2-3. 把问题一一对应到表格。(lookup table 记忆表)
   2-4. 确定问题的计算顺序。(computational sequence 计算顺序)
   2-5. 确定初始值、计算范围。(initial states / boundary 初始状态/计算边界)
3. 事件,主要有两种方式:
   3-1. Top-down 自上而下   递归
   3-2. Bottom-up 自下而上   循环迭代
  递归 迭代
优点 代码可读性高,易理解
不必考虑子问题的依赖关系和计算顺序
当仅需求解一部分子问题时 更快
代码更
没有递归负载,执行更
滑动窗口
缺点 不能使用滑动窗口
可能栈溢出
可读性差,不直观
需注意子问题依赖关系和计算顺序

设计步骤

(1)划分阶段
(2)确定状态空间和状态变量  通常是数组(1维或多维)下标指决策,元素 指状态
(3)确定决策并写出状态转移方程  递推公式
(4)寻找边界条件

 

sarafina527
发布了75 篇原创文章 · 获赞 3 · 访问量 3502
私信 关注

本文链接http://element-ui.cn/news/show-1438.aspx