概念
动态规划(Dynamic Programming)，是一种分阶段求解的方法。
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现. 关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择 然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态
转移方程式) 我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度。
动态规划中有三个重要概念：
1）最优子结构
2）边界
3）状态转移公式（递推方程）dp方程
经典问题
再谈斐波那契数列
优化递归：
image.png
通过上边的递归树可以看出在树的每层和上层都有大量的重复计算，可以把计算结果存起来，下次再用的时候就不用再计算了，这种方式叫记忆搜索，也叫做备忘录模式
代码如下：
package com.david.alth.dp;
/**
* 斐波那契数列： 递归分治+记忆搜索(备忘录)
*/
public class Fib2 {
//用于存储每次的计算结果
static int[] sub=new int[10];
public static int fib(int n){
if(n<=1) return n; //没有计算过则计算
if(sub[n]==0){
sub[n]=fib(n-1)+fib(n-2);
}
//计算过直接返回
return sub[n];
}
public static void main(String[] args) {
System.out.println(fib(9));
}
}
dp方程：
image.png
if(i<2) 则dp[0] = 0, dp[1] = 1
if(i>=2) 则dp[i] = dp[i - 1] + dp[i - 2]
最优子结构： fib[9]=finb[8]+fib[7]
边界：a[0]=0; a[1]=1;
dp方程：fib[n]=fib[n-1]+fib[n-2]
实现代码如下：
/**
* 斐波那契数列 自底向上递推
*/
public class Fib3 {
public static int fib(int n){
int a[] = new int[n+1];
a[0] = 0;
a[1] = 1;
int i;
// a[n]= a[n-1]+a[n-2]
for(i=2;i<=n;i++){
a[i] = a[i-1] + a[i-2];
}
// i已经加1了，所以要减掉1
return a[i-1];
}
public static void main(String[] args) {
System.out.println(fib(9));
}
}
使用动态规划四个步骤:
- 把当前的复杂问题转化成一个个简单的子问题（分治）
- 寻找子问题的最优解法（最优子结构）
- 把子问题的解合并，存储中间状态
- 递归+记忆搜索或自底而上的形成递推方程(dp方程)
时间复杂度
新的斐波那契数列实现时间复杂度为O(n)
优缺点
优点：时间复杂度和空间复杂度都相当较低
缺点：难，有些场景不适用
适用场景
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
网友评论