-2c57ec47146f40cbabf9adc9f224a0a3.jpg)
动态规划
在数学上的递归表示的问题在计算机上都可以转化为递归的算法，在大多数情况下来看，能够对朴素的穷举提升效率，但是在实际情况来看呢，计算机递归内会有大量的重复计算，导致递归的效率很低，这时候针对朴素的穷举的递归就是不友好的了，需要我们去对其提供一些帮助。这种技巧就是动态规划
- 基于缓存子问题的结果的方式去优化递归
- 建立DpTable去存储子问题的结果，讲递归改为非递归算法
在学习数据结构和算法的开篇，计算for循环的时间复杂度时，曾做过计算x的斐波那契数,计算公式如下：
public int fib(int x){
if (x==1||x==2) return 1;
return fib(x-1)+fib(x-2);
}
当时老师讲课的时候也是按照上面的解法写，给定base值，然后去找x的斐波那契数，例如要寻找F(20)的值，找寻过程呢如下图所示。很显然从左边计算计算F(19)就已经计算了F(18)的值，但是在计算右边的F(18)还需要重复计算。不难发现这种穷举的过程与很多重复计算，这就是我们要优化的地方。递归算法之所以慢是，完全模拟了整个数学公式的递推过程。从下面这个图来看，容易计算基本上耗时是暴涨的。如果要是编译器能在模拟递推过程中记录下这个值，这个效率的提升将会很显著。
采用方式一的改进如下，使用cache数组来存放子问题的结果,从左边计算计算F(19)就已经计算了F(18)的值，并且存在了cache中，于是在计算右边的F(18)直接送cache中读取即可。
public int fibcache(int x){
int[] cache=new int[x];
return cache(cache,x);
}
public int cache(int[] cache,int x){
if (x==1||x==2) return 1;
if (cache[x]!=0) return cache[x];
cache[x]=cache(cache,x-1)+cache(cache,x-2);
return cache[x];
}
再采取方式二来优化,建立DpTable按照Dp方程自底向上求解。Dp方程就是上述的数学公式。
public int fibDpTable(int x){
int[] DpTable=new int[x];
DpTable[1]=1;
DpTable[2]=1;
for(int i=3;i<=x;i++){
DpTable[i]=DpTable[i-1]+DpTable[i-2];
}
return DpTable[x];
}
进一步可以采用联机计算来避免创建DpTable。来实现求斐波那契数。
/**
* 联机计算
* @param x
* @return
*/
public int fibDpOnline(int x){
int result=1,left=1,reght=1;
for(int i=3;i<=x;i++){
result=left+reght;
left=reght;
reght=result;
}
return result;
}
上述叙述的是一种优化的技巧(找出重叠子问题)，实际上动态规划一般是解决求最值问题，比如说让你求最大子序列和，最长回文子串等，那个怎么知道最大 或者最长呢，就是要注意穷举所有的子序列的和。穷举所有的回文子串，然后再对这些子问题求MAX或者MIN,通过子问题求得最值，虽然理解动态规划需要进行穷举，但是罗列所有的穷举值没有状态方程是列不出来的。
动态规划类问题就是通过暴力破解来选出来状态方程，然后根据初始状态，迭代状态方程，选出来穷举值，在穷举值求出最值。
针对斐波那契而言呢，不能算是动态规划求最值问题，那再来看下零钱兑换，最大子序列和，和最经典的背包问题这三道题。
零钱兑换
给你 x 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，返回 -1。
分析:
取一个硬币coin，总金额就等于amount-coin，如果amount==0，那么返回0，如果amount<0,那么返回-1，
首先来一手递归循环搞事情。用于我们去定位状态方程。时间复杂度O(n^2)。
public int coin(int[] coins,int amount){
if(amount==0)return 0;
if(amount<0)return -1;
int min=Integer.MAX_VALUE;
for(int i=0;i<coins.length;i++){
int subAmount=amount-coins[i];
if(subAmount<0)continue;
//这个1是取了一次。
min=Math.min(min,coin(subAmouunt)+1);
}
return min;
}
按照上述的动态规划的技巧去解决，先用缓存保存一下冗余计算的值。得到如下代码。
public int coin(int[] coins,int amount){
int[] cache=new int[amount];
return coinCache(cache,coins,amount);
}
public int coinCache( int[] cache,int[] coins,int amount){
int result=Integer.MAX_VALUE;
if (amount==0) return 0;
if (amount<0) return -1;
if (cache[amount]!=0) return cache[amount];
for (int i=0;i<coins.length;i++){
int sumamount=coinCache(cache,coins,amount-coins[i]);
if (sumamount==-1) continue;
result=Math.min(result,sumamount+1);
}
cache[amount]=result!=Integer.MAX_VALUE?result:-1;
return cache[amount];
}
进一步的推算可以得到状态方程。
你是否觉得动态规划有点熟练了呢，称热打铁。使用DpTable来处理一下。
public int coinCache( int[] coins,int amount){
int[] coinsDptable=new int[amount+1];
for (int j=1;j<coinsDptable.length;j++){
coinsDptable[j]=amount+1;
}
coinsDptable[0]=0;
for(int len=0;len<coinsDptable.length;len++){
for (int i=0;i<coins.length;i++){
if (len-coins[i]<0)continue;
coinsDptable[len]=Math.min(coinsDptable[len],1+coinsDptable[len-coins[i]]);
}
}
return coinsDptable[amount]==amount+1?-1: coinsDptable[amount];;
}
最大子序列和
/**
* 最大子序列求和
* O(N^2)
* a[0],a[0]+a[1].....a[0]+a[1]..a[N];取出了本次循环的最大值
* a[1],a[1]+a[2].....a[1]..a[N];取出了本次循环的最大值
* 。。。。。
* a[n];取出了本次循环的最大值
* 然后对所有的最大值做max
*/
public static int findMaxSubSequenceMax(int[] a){
int max=0;
for (int i=0;i<a.length;i++){
int innerSum=0;
for (int j=i;j<a.length;j++){
innerSum+=a[j];
if (innerSum>max){
max=innerSum;
}
}
}
return max;
}
首先来一首二重循环暴力破解，不要看不起二重循环，运用上述的规则求解，规则a[i]=a[i-1]+a[i],根据该规则定义状态方程
public static int findMaxSubSequenceMax(int[] a){
int max=a[0];
for (int i=1;i<a.length;i++){
a[i]=Math.max(a[i-1],0)+a[i]
max=Math.max(max,a[i])
}
return max;
}
背包问题
有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，容量 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
参考资料
- 背包问题 - 维基百科
- 背包问题-笔记整理
- 动态规划与贪婪法题16：背包问题总结 - CSDN
- 背包问题九讲2.0 - 崔添翼
- labuladong的算法小抄
- LeetCode 322 零钱兑换