package 数阵中的最优路径;import java.util.Scanner;public class Main {    /**     * 数值三角形中的最大路径     * 随机产生一个n行的点数值三角形（第k行有k个点，每个点都带有一个正整数，）寻找从顶点开始每一步可沿着左或者右向下的至底部的一条路径，     * 使得该路径的和最大。     *      * 数值三角形中的最大路径的搜索     * 应用动态规划，采用逆推法从低向上逐行反推     * 随机产生的点数值三角形存储在一个二维数组中，同时赋值给b(n,n),这里的数组b(i,j)为点（i,j）到底的最大的数值和     * stm(i,j)表示向左还是向右的路标字符数组，实施逆推法，知道b(i,j),stm(i,j)的值由b的第i+1行的值决定：     *      * 如果b(i+1,j+1) > b(i+1,j)则     * b(i,j) = b(i,j)+b(i+1,j+1)     * stm(i,j) = "R"     *      *      * 如果b(i+1,j+1) <= b(i+1,j)则     * b(i,j) = b(i,j)+b(i+1,j);     * stm(i,j) = "L"     *      * 这样一直到最后所得的b(1,1)就是所求的最优路径的数值和。     * 为了打印最优路径，利用stm数组从上到下查找：先打印a(1,1),如果stm(1,1) = “R”     * 则打印下一个a(2,2)否则打印a(2,1)，一般的对i=2,3,4,.....n;     * 如果stm(i-1,j) = "R",则打印"-R-",a(i,j+1);同时赋值j = j+1;     * 如果stm(i-1,j) = "L"则打印"-L-" ；a(i,j)     *      * @param args     */    public static void main(String[] args) {        Scanner input = new Scanner(System.in);        System.out.println("输入行数：");        int n = input.nextInt();        int i,j,t;        int a[][] = new int[100][100];        int b[][] = new int[100][100];        char[][]stm = new char[100][100];        //打印数字三角形        for(i = 1;i<=n;i++)        {            for(j = 1;j<=40-2*i;j++)            {                System.out.printf("  ");            }                        for(j = 1;j<=i;j++)            {                a[i][j] = (int)(Math.random()*20+1);                b[i][j] = a[i][j];                System.out.printf("%4d",a[i][j]);            }            System.out.println();            }                //逆推求最大值        for(i = n-1;i>=1;i--)                    for(j = 1;j<=i;j++)            {                if(b[i+1][j+1] > b[i+1][j])                {                    b[i][j]+=b[i+1][j+1];                    stm[i][j]=‘R‘;                }else{                    b[i][j]+=b[i+1][j];                    stm[i][j] = ‘L‘;                }            }                                System.out.println("最优路径数值和：="+b[1][1]);        System.out.print("最优路径为："+a[1][1]);        //按照路标引号输出最优路径        j = 1;        for(i = 2;i<=n;i++)        {            if(stm[i-1][j] == ‘R‘)            {                System.out.printf("-R-%2d",a[i][j+1]);                j = j+1;            }else{                System.out.printf("-L-%2d",a[i][j]);            }        }                                                                                                                        }}