アルゴリズム設計と分析:3-9ヨットレンタル問題

2599 ワード
Algorithm Java ダイナミック？プログラム 計算機アルゴリズムの設計と分析
3-9レンタルヨットの問題
問題の説明
長江ヨットクラブは長江にn個のヨットレンタルステーション1,2,3...,nを設置した.観光客はこれらのヨットレンタルステーションでヨットを使用し、下流のどのヨットレンタルステーションでもヨットを返却することができます.ヨットレンタルステーションiからヨットレンタルステーションjまでの間の賃貸料は、r(i,j)r(i,j)、1<=iデータ入力1行目には正の整数n(n<=200)が1つあり、n個のヨットレンタルステーションがあることを示し、次のn−1行はr(i,j)、1<=iJava 
import java.util.Scanner;

public class ZuYongYouTing {

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n;
        int[][] fee;

        while (true){
            n = input.nextInt();
            fee = new int[n][n];

            for(int row=0; row1; row++)
                for(int col=row+1; colfor(int k=2; kfor(int i=0; iint j = i+k;
                    for(int p =i+1; pint tmp = fee[i][p] + fee[p][j];
                        if(fee[i][j] > tmp)
                            fee[i][j] = tmp;
                    }
                }

            System.out.println(fee[0][n-1]);//fee[i][j]:   i      j           ，  fee[0][n-1]    
        }
    }
}

Input & Output 
3
5 15
7
12

Reference
王暁東『コンピュータアルゴリズム設計と分析』(第3版)P 91
hibernate--リレーショナルマッピング
剣指Offer-64:1+2+...+を求めますn