假设某条河有N个游艇出租站1、2、3...N,游客可以在出租站租用游艇,并在下游任何一个出租站归还游艇,出租站i和出租站j之间的租金为R(i,j)其中1<=i<j<=N,试设计一个算法,计算从出租站1到N所需要最少的租金。
出租站输入
出租站个数不要太小就行
租金输入
自动输出结果
public class BoatRentalProblem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入出租站的个数:");
int N = scanner.nextInt();
int[][] R = new int[N][N];
System.out.println("请输入完整的租金矩阵(每行输入对应租金矩阵的一行,每行之间用空格隔开):");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
R[i][j] = scanner.nextInt();
}
}
scanner.close();
int minRent = calculateMinRent(R, N);
System.out.println("从出租站1到出租站" + N + "所需的最少租金为:" + minRent);
}
public static int calculateMinRent(int[][] R, int N) {
int[] dp = new int[N + 1];
for (int i = 2; i <= N; i++) {
dp[i] = R[0][i - 1]; // 初始化dp数组
for (int j = 1; j < i; j++) {
dp[i] = Math.min(dp[i], dp[j] + R[j - 1][i - 1]); // 更新dp数组
}
}
return dp[N];
}
}
代码有一些方面可以进行优化以提高效率和可读性。
输入验证:
代码注释:
变量命名:
N
?重命名为?numStations
,将?R
?重命名为?rentMatrix
?等。动态规划数组初始化:
calculateMinRent
?方法中,dp
?数组被初始化为?new int[N + 1]
。由于Java中数组默认初始化为0,因此显式地将?dp[1]
?设置为0是不必要的。循环优化:
异常处理:
输出格式:
代码重构:
使用Java 8+特性:
关闭Scanner: