游船费问题-动态规划

问题描述

某旅游城市在长江边开辟了若干个旅游景点。一个游船俱乐部在这些景点都设置了游船出租站，游客可在这些游船出租站租用游船，并在下游的任何一个游船出租站归还游船，从一个游船出租站到下游的游船出租站间的租金明码标价的。你的任务是为游客计算从起点站到终点站间的最少租船费用。

输入

输入有若干组测试数据，每组测试数据的第一行上有一个整数n，(1<=n<=100)，表示上游的起点站0到下游有n个游船出租站1、2、…、n。接下来有n行，这n行中的第1行有n个整数，分别表示第0站到第1、2、3、…、n站间的游船租金；第2行有n-1个整数，分别表示第1站到第2、3、4、…、n站间的游船租金；…；第n-1行有2个整数，表示第n-2站到第n-1、n站间的游船租金；第n行有1个整数，表示第n-1站到第n站间的游船租金。一行上两个整数之间是用空格隔开的。当游船租金是-1时，表示这两个站之间无直通航线。两组测试数据之间无空行。

输出

对输入中描述的每组测试数据，先在一行上输出“Case #:”，其中“#”测试数据的编号（从1开始编）。对输入文件中的每组测试数据，在输出文件中输出一行，内容是该情况下游客从起点站到终点站间的最少租船费用。

输入样例

3 2 3 6 1 3 2 3 4 7 9 4 5 6

输出样例

Case 1: 5 Case 2: 9

算法思路

用r[i][j]记录第i站到第j站的直达游船租金，f[i]记录从起点第0站到第i站的最少游船租金。那么从第0站到第i站有两种方式到达：

直达：r[0][i] 中转：在第k站进行中转，从第0站到第k站最少租金f[k]，从第k站到第i站直达租金r[k][i] 则求解的从第0站到第i站的最少租金为： f ( i ) = { m i n 0 < k < i ( f [ k ] + r [ k ] [ i ] , r [ 0 ] [ i ] ) i > 0 r [ 0 ] [ i ] i = 0 f(i)=egin{cases} min_{0<k<i} (f[k]+r[k][i],r[0][i])& i>0 \ r[0][i ]& i=0 end{cases} f(i)={ min0<k<i(f[k]+r[k][i],r[0][i])r[0][i]i>0i=0

从起点（第0站开始），首先计算到第1站的最优值f(1)，因为没有中转站，所以可以直接得到。计算起点到第2站的时候，就要取直达和经第1站中转的最小值。计算起点到第3站的时候，就要取直达和经第1站中转、经第2站中转的最小值。以此类推，直到求解出f[n]，即起点到终点的费用。这样先解决了子问题，然后逐步求出了待求解问题。

代码实现

public class Main {
          
   

    //上游的起点站0到下游有n个游船出租站
    private static int n;

    // r[i][j]表示从i直达j+1站的租金
    private static int[][] r;

    // f[i]表示从0到i站的最少租金
    private static int[] f;

    public static void main(String[] args) {
          
   
        // 读取键盘输入
        Scanner sc = new Scanner(System.in);
        int count = 0;
        while (true) {
          
   
            count++;
            n = sc.nextInt();
            r = new int[n][n];
            for (int i = 0; i < n; i++) {
          
   
                for (int j = i; j < n; j++) {
          
   
                    r[i][j] = sc.nextInt();
                }
            }
            System.out.println("Case " + count + ":
" + solution() + "
");
        }
    }

    public static int solution() {
          
   
        // f[0]=0,f[n]表示起点到终点
        f = new int[n + 1];
        // 从1到n的最少费用，求n要用到n-1，求n-1...
        for (int i = 1; i <= n; i++) {
          
   
            // 0到i直达
            f[i] = r[0][i - 1];
            for (int k = i - 1; k > 0; k--) {
          
   
                // 0到i直达或者经过k中转
                f[i] = min(f[i], f[k] + r[k][i - 1]);
            }
        }
        return f[n];
    }
}