【算法】动态规划(三)——解题方法与解题思路
0.前言
动态规划最核心的思想就是:拆分子问题,记住过往,减少重复计算。
动态规划可以从下面的参考网上的一个例子:
A :"1+1+1+1+1+1+1+1 =?" A :"上面等式的值是多少" B :计算 "8" A : 在上面等式的左边写上 "1+" 呢? A : "此时等式的值为多少" B : 很快得出答案 "9" A : "你怎么这么快就知道答案了" A : "只要在8的基础上加1就行了" A : "所以你不用重新计算,因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
1.动态规划的两种基本形式
一般求解的方式有两种:①自顶向下的备忘录法 ②自低向上
为了说明动态规划的这两种方法,举个简单例子:
【题目描述】已知斐波那契数列第n项。0,1,1,2,3,5,8.......输出斐波那契数列的第n项。
【输入描述】一个正整数n。表示第n项。
【输出描述】第n项是多少。
【样例输入】4
【样例输出】2
我们前面解过这个题目,很快可以写出递归函数来。
nt calculate(int n) { if(n==1) return 0;//判断是否到达递归边界n=1 else if(n==2) return 1;//判断是否到达递归边界n=2 else return calculate(n-1)+calculate(n-2);//未到达继续递归 }
我们分析一下递归的流程,加入计算n=5
[图片=http:??]
上面的递归树中的每一个子节点都会执行一次,很多重复的节点被执行,calculate(2)被重复执行了3次。由于调用每一个函数的时候都要保留上下文,所以空间上开销也不小。这么多的子节点被重复执行,如果在执行的时候把执行过的子节点保存起来,后面要用到的时候直接查表调用的话可以节约大量的时间。
下面看看动态规划如何求解斐波那契数列问题?
①自顶向下——备忘录法
参考代码:
public class Solution { //使用哈希map,充当备忘录的作用 Map<Integer, Integer> tempMap = new HashMap(); public int numWays(int n) { // n = 0 也算1种 if (n == 0) { return 1; } if (n <= 2) { return n; } //先判断有没计算过,即看看备忘录有没有 if (tempMap.containsKey(n)) { //备忘录有,即计算过,直接返回 return tempMap.get(n); } else { // 备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录map中,对1000000007取余(这个是leetcode题目规定的) tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007); return tempMap.get(n); } } }
备忘录法也是比较好理解的,创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值,在递归的时候如果发现前面fib(n)的值计算出来了就不再计算,如果未计算出来,则计算出来后保存在数组中,下次在调用fib(n)的时候就不会重新递归了。比如上面的递归树中在计算fib(6)的时候先计算fib(5),调用fib(5)算出了fib(4)后,fib(6)再调用fib(4)就不会在递归fib(4)的子树了,因为fib(4)的值已经保存在其中了。
②自底向上的动态规划
备忘录法还是利用了递归,上面算法不管怎样,计算fib(6)的时候最后还是要计算出fib(1),fib(2),fib(3)…,那么何不先计算出fib(1),fib(2),fib(3)…,呢?这也就是动态规划的核心,先计算子问题,再由子问题计算父问题。
动态规划跟带备忘录的递归解法基本思想是一致的,都是减少重复计算,时间复杂度也都是差不多。但是呢:
带备忘录的递归,是从f(10)往f(1)方向延伸求解的,所以也称为自顶向下的解法。
动态规划从较小问题的解,由交叠性质,逐步决策出较大问题的解,它是从f(1)往f(10)方向,往上推求解,所以称为自底向上的解法。
动态规划有几个典型特征,最优子结构、状态转移方程、边界、重叠子问题。在题中:
f(n-1)和f(n-2) 称为 f(n) 的最优子结构
f(n)= f(n-1)+f(n-2)就称为状态转移方程
f(1) = 1, f(2) = 2 就是边界啦
比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。
我们来看下自底向上的解法,从f(1)往f(10)方向,想想是不是直接一个for循环就可以解决啦,如下:
int fibonacciDP2(int n) { // 动态规划使用数组 int *a = new int[n+1]; a[0] = 0, a[1] = 1; for (int i = 2; i < n+1; i++) { a[i] = a[i - 1] + a[i - 2]; } return a[n];}
动态规划的解题套路
什么样的问题可以考虑使用动态规划解决呢?
如果一个问题,可以把所有可能的答案穷举出来,并且穷举出来后,发现存在重叠子问题,就可以考虑使用动态规划。
比如一些求最值的场景,如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等,都是动态规划的经典应用场景。
动态规划的解题思路
动态规划的核心思想就是拆分子问题,记住过往,减少重复计算。 并且动态规划一般都是自底向上的,因此到这里,基于问题,动态规划的思路:
穷举分析
确定边界
找出规律,确定最优子结构
写出状态转移方程
简单模板:
dp[0][0][...] = 边界值 for(状态1 :所有状态1的值){ for(状态2 :所有状态2的值){ for(...){ //状态转移方程 dp[状态1][状态2][...] = 求最值 } } }