区间动态规划问题（游艇租用问题）

区间动态规划问题（游艇租用问题）

问题描述

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。

编程任务

对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i<j£n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。

数据输入

由文件提供输入数据。文件的第1行中有1个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1<=i<j<=n。

(例如：
3

5 15

7

表示一共有3个出租站点，其中

第1个站点到第2个的租金为5

第1个站点到第3个的租金为15

第2个站点到第3个的租金为7

)

模板

这是一个区间动态规划问题，状态的转移发生在一个个区间上。

针对该类题目，可从以下模板中找寻思路：

1. 阶段（区间长度）

设区间长度为d，

• 当区间是1 =》 2的时候，此时区间长度为2；

• 当区间是1 =》 3的时候，此时区间长度为3。

很显然，如果区间长度小于3，那就可以直接取值，不需要状态转移

所以我们只需要考虑区间长度 > 3 的情况

即 d = 3,4,…n （当 d = 2 的时候，也就是1-2,2-3，不需要求解，直接读取数组的值即可）

2. 状态

举例：当 区间长度d = 3 ，站点数n = 6 的时候

起点i的取值：1-3,2-4,3-5,4-6，不能再取5了，因为最大值n = 6，而5-6不能取到d=3，因
此i的取值为 1 ~ n - d + 1。

终点j的取值：i ~ n - i + 1

而中间可能停靠的站点k 就在i和j之间取值

3. 决策

状态转移方程：

用dp [ i ] [ j ]表示从i到j的最少费用

dp [ i ] [ j ] = min{dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k ] [ i ]}

扩展

如果需要记录最短费用的路径上，是停靠了哪些站点呢？

那就再开一个二维数组 s[ i ] [ j ]，当发生状态转移的时候，就记录下当前的k值。

然后通过递归，依次找到其他不为0的k值。

public static void minPath(int i , int j , int [][]path, int []pathPoint,int pathIndex) {if(path[i][j] == 0){} // 什么都不做else {pathPoint[pathIndex++] = path[i][j]; // 加入到数组minPath(i,path[i][j],path,pathPoint,pathIndex); // 左边区间minPath(path[i][j],j,path,pathPoint,pathIndex); // 右边区间}}

完整代码：

package algorithm;import java.io.*;
import java.util.Arrays;
import java.util.Scanner;public class experiment_03 {public static void main(String[] args) {String srcPath = &#";String targetPath = &#";int cnt = 0;int []arr = new int[100];int [][]dp = new int[100][100]; // dp数组 表示从i到j最少的费用int [][]path = new int[100][100]; // 记录中间停靠站点k值的二维数组int []pathPoint = new int[100]; int pathIndex = 0; // 记录停靠的站点try {Scanner scanner = new Scanner(new FileReader(&#"));while(scanner.hasNextInt()) {arr[cnt++] = Int();}} catch (FileNotFoundException e) {e.printStackTrace();}int n = arr[0]; // 站点总数cnt = 0;for(int i = 1 ; i <= n ; i++) { // dp数组初始化 上三角二维数组for(int j = i + 1; j <= n ; j++) {dp[i][j] = arr[++cnt];}}System.out.println("最少的花费为：" + minFare(n,dp,path));minPath(1,n,path,pathPoint,pathIndex);System.out.printf("经过的站点为：1 ");printPath(pathPoint);System.out.print(n);}public static int minFare(int n ,int [][]dp , int [][]path) {for(int d = 3; d <= n ; d++) { // 1. 区间长度for (int i = 1 ; i <= n - d + 1; i++) { // 2. 起点的取值范围int j = i + d - 1; // 3. 起点对应的终点的值for(int k = i + 1 ; k < j ; k++) { // 4. 可能停靠的站点
//                  dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);if(dp[i][k] + dp[k][j] < dp[i][j]) {dp[i][j] = dp[i][k] + dp[k][j];path[i][j] = k;}}}}return dp[1][n];}// 递归求出可能停靠的站点public static void minPath(int i , int j , int [][]path, int []pathPoint,int pathIndex) {if(path[i][j] == 0){}else {pathPoint[pathIndex++] = path[i][j];minPath(i,path[i][j],path,pathPoint,pathIndex);minPath(path[i][j],j,path,pathPoint,pathIndex);}}// 打印出最少花费的路径public static void printPath(int []pathPoint) {int cnt = 0;while(pathPoint[cnt++] != 0);int []arr = new int[cnt-1];for(int i = 0 ; i < cnt-1 ; i++) arr[i] = pathPoint[i];Arrays.sort(arr);for(int i = 0 ; i < cnt-1 ; i++) System.out.printf(arr[i] + " ");}}

注意：把文件中的内容按照int数字读出来的方法

Scanner scanner = new Scanner(new FileReader(&#"));while(scanner.hasNextInt()) {arr[cnt++] = Int();}

在找到此文件读取方法之前，笔者一直在用一整行读取或者是按照1个字节读取，在这个地方耽误了很久时间。

实际上无论是一整行还是1个字节，对于上三角存放文件中的数组都不方便！