Go语言视频零基础入门到精通

javalearner

首先让我们看一个例子：
例1：如下图有一个数字三角阵，请编一个程序计算从顶点至底的某处的一条路径，使该路径所经过的数字的和最大。每一步可沿左斜线向下或右斜线向下走。
           7
       5     3
    4     2    1
  2     1    3    7

    这个问题的实质实际上是一个有向图中最长路经问题，可以用经典的图论算法或者搜索来解决。

     考虑如何用搜索法来解这道题，从第一个点开始扩展，每次扩展2个可行节点，直到达到数字三角形的底部，从所有的可行路径中找出最优值，这样做的复杂度是o(2^n)，当n很大的时候，普通的搜索法将不可行。

      观察发现，搜索的效率低下很大程度上是因为做了大量的重复运算，因为对于任何一个节点，从他开始向下拓展的最优值是确定的，这启发了我们应当充分利用之前的运算结果。  
  
   
   
     
   

     
   
  
下面我们来进行深入的分析，假如已经走第I行第J列，此时最大累加和S[I，J], 应选S[I-1，J-1]，S[I-1，J+1]中较大者再加上（I，J）处的值A[I，J]，即下式

   S[I，J]=A[I，J]+MAX（S[I-1，J-1]，S[I-1，J+1]）

   所以我们可以从第一行开始，向下逐行推出每一处位置的最大累加和S，最后从底行的N个S中选出最大的一个即为所求，这种算法的复杂度为o(n^2)，比较搜索法，已经大大的降低了，这种充分利用已经计算出结果的方法，就叫做动态规划。   通过上面的例子，我们对“动态规划”有了一个初步认识，它所处理的问题是一个“多阶段决策问题”。我们现在对一些概念进行具体定义：

状态（State）：
    它表示事物的性质，是描述“动态规划”中的“单元”的量。如例1中的每个节点（指节点处的最大值）都为单个的状态。

阶段（Stage）：
    阶段是一些性质相近，可以同时处理的状态集合。通常，一个问题可以由处理的先后次序划分为几个阶段。如例1中的问题，每一行若干节点组成一个阶段。一个阶段既可以包含多个状态，也可以只包含一个状态。描述各阶段状态的变量称为状态变量，例1中可用S[4 , j]来表示第四阶段（即第四行）走到第j列的最大值，即第四阶段状态变量。

状态转移方程：
     是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态的方程，是“动态规划”的中心。

如例1中： S[I，J]=A[I，J]+MAX（S[I-1，J]，S[I-1，J+1]）

决策（Decision）：
    每个阶段做出的某种选择性的行动。它是我们程序所需要完成的选择。如例1中MAX（S[I-1，J]，S[I-1，J+1]）

动态规划所处理的问题是一个“多阶段决策问题”，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线） 从上面的讲解我们可以发现：动态规划并不像一种算法，而更像一种思考方式。 下面，我们来讨论动态规划的应用范围，要确定一个问题是否能用动态规划，需要考虑两个方面：

一：最优子结构
即一个问题的最优解只取决于其子问题的最优解，也就是说，非最优解对问题的求解没有影响。我们再来看一个问题：

例二：
     有4个点，分别是A、B、C、D，相邻两点用两条连线，表示两条通行的道路，给出每条道路的长度。我们定义从A到D的所有路径中，长度除以4所得余数最小的路径为最优路径。求一条最优路径。
     很多初学者往往会认为这道题也可以采用动态规划的方法，但实际并不如此，考虑这种情况:
假如A-B的两条道路分别为2，3,B-C的两条道路分别为1，4。如果采用动态规划，节点B的最优值为2，节点C的最优值2，但际上到达C的最优值应该是0，即3-1这条线路。
也就是说，C的最优取值不是由B的最优取值决定的，其不具有最优子结构。

由此可见，并不是所有的“决策问题”都可以用“动态规划”来解决。所以，只有当一个问题呈现出最优子结构时，“动态规划”才可能是一个合适的侯选方法。 二：无后效性
即一个问题被划分阶段后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。 例三：对于一个由数字组成的二叉树，求由叶子到根的一条路径的数字和的最大值.
            7
          3  8
        8  1  0
     2   7  4  4
   4   5  2  6  5

从上往下计算，对于每一点，只需要保留从上面来的路径中和最大的路径的和即可。
因为在它下面的点只关心到达它的最大路径和，不关心它从那条路经上来的。

程序：(为了省时间，数字输入部分省了）

1. import java.util.Scanner;
   
2. 
   
3. public class Test{
   
4.   public static void main(String args[]){
   
5.      int n=5;
   
6.     int a[][]={{0,0,0,0,0,7,0,0,0,0,0},
   
7.                {0,0,0,0,3,0,8,0,0,0,0},
   
8.                {0,0,0,8,0,1,0,0,0,0,0},
   
9.                {0,0,2,0,7,0,4,0,4,0,0},
   
10.                {0,4,0,5,0,2,0,6,0,5,0}};
    
11.     int s[][]=new int[5][11];  
    
12.     s[0][5]=a[0][5];
    
13.     for(int i=1;i< n;i++){
    
14.      for(int j=1;j< 10;j++){
    
15.        s[i][j]=Math.max(s[i-1][j-1],s[i-1][j+1])+a[i][j];
    
16.      }
    
17.     }
    
18.     System.out.println("原始数据");
    
19.     for(int i=0;i< n;i++){
    
20.      for(int j=0;j< 11;j++){
    
21.        System.out.printf("%-4d",a[i][j]);
    
22.     }
    
23.     System.out.println();
    
24.    }
    
25.    
    
26.    System.out.println();
    
27.    System.out.println("对应的最大路径");
    
28.    for(int i=0;i< n;i++){
    
29.      for(int j=0;j< 11;j++){
    
30.        System.out.printf("%-4d",s[i][j]);
    
31.     }
    
32.     System.out.println();
    
33.    }
    
34.    System.out.println();
    
35.    System.out.println("最长路径的值为：");
    
36.     System.out.println(max(s[n-1]));
    
37. 
    
38. }
    
39.   public static int max(int b[]){
    
40.     int max=b[0];
    
41.    for(int i=1;i< b.length;i++){
    
42.      if(b[i]>max) max=b[i];
    
43.    }
    
44.    return max;
    
45. }
    
46.      
    
47. }
    

复制代码

运行结果：

  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/25/000421609.zip