动态规划-点数值三角形的最优路径搜索 java

1案例提出

在一个n行的点数值三角形中，寻找从顶点开始每一步可沿左斜（L）或右斜（R）向下至底的一条路径，使该路径所经过的点的数值和最小。

例如，n=7时给出的点数值三角形如图所示，如何寻找从项到底的数值和最小路径？该最优路径的数值和为多少？    

思路：

问题：求 d(1,1)典型的递归问题。a(i, j)出发，下一步只能走a(i+1,j)或者a(i+1, j+1)。故对于N行的三角形：if ( i== N) d(i,j) = D(i,j)else d( i, j) = Max{ d(i＋1,j), d(i+1,j+1) } + a(i,j)

package basic_PRactice;import java.util.Scanner;public class anlian_bfs {	public static void main(String[] args) {		int a[][]=new int[50][50];          //各个点的数据		int b[][]=new int[50][50];         //数组b[i,j]为点(i,j)到底的最小数值和		char stm[][]=new char[50][50];      //字符数组stm[i,j]指明点(i,j)向左或向右的路标		int n,i,j;		Scanner in=new Scanner(System.in);		n=in.nextInt();		  for(i=1;i<=n;i++)		   {for(j=1;j<=36-2*i;j++) System.out.print(" ");//让数字在控制台中间输出		    for(j=1;j<=i;j++)		      {a[i][j]=(int)(1+Math.random()*(50-1+1));//产生1-50的随机数		      System.out.print(a[i][j]+"  ");    	// 打印n行数字三角形  		      }		    System.out.println();		}		  System.out.println("请在以上点数值三角形中从顶开始每步可左斜或右斜至底");		System.out.println("寻找一条数字和最小的路径./n ");		   		  for(j=1;j<=n;j++) b[n][j]=a[n][j];      //边界条件，a[n][j]是底边，所以，b[n][j]开始走，只能走一步		  for(i=n-1;i>=1;i--)                      	// 逆推得b[i][j]  从最底层推到b[1][1]		     for(j=1;j<=i;j++)		       if (b[i+1][j+1]<b[i+1][j])		          {b[i][j]=a[i][j]+b[i+1][j+1];stm[i][j]='R';}		       else  {b[i][j]=a[i][j]+b[i+1][j];stm[i][j]='L';}		  System.out.println("最小路径和为:/n"+b[1][1]);  	// 输出最小数字和  		 System.out.print("最小路径为:/n"+a[1][1]);		  j=1;    	// 输出和最小的路径  		  for(i=2;i<=n;i++)		     if(stm[i-1][j]=='R') 		        { 		        System.out.print("-R-"+a[i][j+1]);j++;}		     else		        System.out.print("-L-"+a[i][j]);		System.out.println();	}}输入：5
输出：                                  44                                  5  23                                25  31  13                              46  38  4  9                            22  9  4  9  8  请在以上点数值三角形中从顶开始每步可左斜或右斜至底寻找一条数字和最小的路径. 最小路径和为:88最小路径为:44-L-5-R-31-R-4-L-4