动态规划

引：慢慢就步入了算法导论的高级设计与分析技术模块，先来看看动态规划。ps:快毕业的心情org。

动态规划总说

动态规划虽然与分治方法相似，但是它能够解决子问题重叠的情况，这样就提高了效率。它通常是用来求解最优化的问题。求得是一个最优解。一般按如下4个步骤来设计一个动态规划算法。

1. 刻画一个最优解的结构特征
2. 递归地定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造出一个最优解

钢条切割

先看以前常用的分治方法即自顶向下方法,代码如下：

public class CutRod {
//a[i]表示长度为i的钢条利润是多少
public int[] a = new int[]{1,5,8,9,10,17,17,20,24,30};
//自顶向下递归设计
public int cutRod(int[] a,int n) {
if(n == 0){
return 0;
}
int q = 0;
for (int i = 0; i<n; i++){
q = max(q,a[i]+cutRod(a,n-1-i));
}
return q;
}
//求最大值函数
public int max(int a, int b){
if(a>b){
return a;
} else {
return b;
}
}
public static void main(String[] args) {
CutRod cut = new CutRod();
int lost = cut.cutRod(cut.a,10);
System.out.println(lost);
}
}

问题：反复地用相同的参数值对自身进行递归调用，造成了运行时间为n的指数函数。

为了解决这个问题，我们可以采用动态规划方法求解最优钢条切割问题。

1. 采用带备忘的自顶向下法
   核心是利用一个数组存储已经求解过的最优解，避免了重复的计算，具体的代码如下：

   public class MemoizedCutRod {
   //a[i]表示长度为i的钢条利润是多少
   public int[] a = new int[]{1,5,8,9,10,17,17,20,24,30};
   //带备忘的自顶向下函数
   public int memoizedCutRod(int[] a,int n){
   //创建一个备忘的数组存储一个之前计算过的最优解
   int[] r = new int[n];
   //初始化数组
   for (int i : r) {
   i = 0;
   }
   //借助辅助函数计算
   return memoizedCutRodAux(a, n, r);
   }
   //带备忘的自顶向下法辅助函数
   public int memoizedCutRodAux(int[] a,int n,int[] r) {
   //定义利润
   int q = 0;
   if(n == 0){
   return 0;
   }
   //判断原先是否已经计算过，若计算过就不用再计算
   if(r[n-1] >0){
   return r[n-1];
   }else {
   for (int i = 0; i<n; i++){
   q = max(q,a[i]+memoizedCutRodAux(a, n-1-i, r));
   }
   }
   r[n-1] = q;
   return q;
   }
   //求最大值函数
   public int max(int a, int b){
   if(a>b){
   return a;
   } else {
   return b;
   }
   }
   public static void main(String[] args) {
   MemoizedCutRod cut = new MemoizedCutRod();
   int lost = cut.memoizedCutRod(cut.a, 10);
   System.out.println(lost);
   }
   }

2. 采用由底向上的方法
   核心是从小算到大算出每一个长度的最优解，然后返回想要的长度的最优解。代码如下：

   public class BottomUpTopCutRod {
   //a[i]表示长度为i的钢条利润是多少
   public int[] a = new int[]{1,5,8,9,10,17,17,20,24,30};
   public int bottomUpTopCutRod(int[] a, int n){
   int[] r = new int[n+1];
   //长度为0的时候，收益为0
   r[0] = 0;
   int q = 0;
   for(int i = 0; i<n; i++){
   for(int j = 0; j<=i; j++){
   q = max(q,a[j]+r[i-j]);
   }
   r[i+1] = q;
   }
   return r[n];
   }
   //求最大值函数
   public int max(int a, int b){
   if(a>b){
   return a;
   } else {
   return b;
   }
   }
   public static void main(String[] args) {
   BottomUpTopCutRod cut = new BottomUpTopCutRod();
   int lost = cut.bottomUpTopCutRod(cut.a, 10);
   System.out.println(lost);
   }
   }

优势：实现了运行时间复杂度n*n

动态规划原理

适用应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠

最优子结构

如果一个问题的最优解包含其子问题的最优解，我们就称这个问题具有最优子结构性质。例如：无权最短路径。

重叠子问题

如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。例如钢条切割。

总结

慢慢懂一点小算法思想。