OBST.java

import java.util.*;

public class Main {
    static double minAvg;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("輸入機率 用,相隔。");
        String input = sc.nextLine();
        String[] inputArray = input.split(",");
        double[] inputFrequency= new double[inputArray.length];

        for(int i = 0;i < inputFrequency.length;i++) {
            inputFrequency[i] = Float.parseFloat(inputArray[i]);
        }

        int n = inputFrequency.length ;

        int [][]R = new int[n+1][n+1];

        double A [][] = optst(n,inputFrequency,R);

        showAtable(A);
        System.out.println();
        System.out.println();

    }

    static double[][] optst(int n, double p[],int R[][]) {
        int j,diagonal;
        double [][]A = new double[n+1][n+1];
        for (int i=0; i<n; i++) {
            A[i+1][i+1] = p[i];
            R[i+1][i+1] = i;
        }
        showAtable(A);
        System.out.println();
        System.out.println();

        for(diagonal=1; diagonal<=n-1; diagonal++) {
            for(int i=1; i<=n-diagonal; i++) {
                j = i + diagonal;
                double minimum = Double.MAX_VALUE;
                double sum = 0;
                int minr = 0;
                for(int k=i; k<j; k++) {
                    if (A[i][k-1] + A[k+1][j] < minimum) {
                        minimum = A[i][k-1]+A[k+1][j];
                        minr = k;
                    }
                    sum += p[k];
                }
                A[i][j] = minimum + sum;
                R[i][j] = minr;
            }
        }
        return A;
    }


    //單純打印表
    static void showAtable(double a[][]) {
        for(int i=0;i<a.length;i++) {
            System.out.printf("\t  %d\t",i);
        }
        System.out.println();
        for(int i=0;i<a.length;i++)
            System.out.print("---------");
        System.out.println();

        for(int i=0;i<a.length;i++) {
            for(int z=0;z<a.length;z++) {
                if(z==0) {
                    System.out.printf("%d | %.3f" + "\t", i, a[i][z]);
                }else{
                    System.out.printf("%.3f" + "\t", a[i][z]);
                }
            }
            System.out.println();
        }

    }


}