问题描述：

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

一、输入格式

       第一行表示有n个站点，接下来n-1行是r( i , j)。

二、输出格式

       输出最从游艇出租站1到出租站n所需的最少租金。

1.输入样例：

3
5 15
7

2.输出样例：

12

三、思路：

1.暴力算法：

        很容易想到，我们可以用一个三重循环来遍历所有的选择，取最小的花费路线进行输出(num数组中读取输入的数据)：

#include<bits/stdc++.h>
const int N = 1001;
using namespace std;

int n;
int num[N][N] = {0};

void readin(){
	for(int i = 1; i <= n - 1; i++){
		for (int j = i + 1; j <= n; j++)
			cin >> num[i][j];               
	}
}
int deal_one(){
	for(int r = 2 ; r <= n ; r++){
		for(int i = 1 ; i <= n - r + 1 ; i++){
			int j = i + r - 1;
			for(int k = i ; k <= j ; k++)
				num[i][j] = min(num[i][j] , num[i][k] + num[k][j]);
		}
	}
	return num[1][n];
} 

int main(){
	cout << "请输入出租站个数：\n";
	cin >> n;
	readin();
	cout << "暴力：\n"; 
	cout << deal_one();
} 

2.动态规划：

        1.我们容易发现，在上面的方法中，存在着很多可以优化的地方：比如说我们这道题目问的是从1 到 n 的最小花费，所以说我们可以设置一个dp数组，用dp[ i ]来表示从 1 到 i 的最优解。我们找到从 1 到 i 的最优解之后，我们要得到从 1 到 n 的最优解，只需要改变 i 的值来对比即可。显然我们用一个N的空间来换取了$n^3$ 到 $n^2$转变的时间复杂度。
        2.状态的定义：

		dp[ i ]表示从1 到 i 我们的最优选择；

        3.状态转移方程：

		dp[i] = min(dp[i] , dp[j] + dp[j] + num[j][i]);

代码如下：

#include<bits/stdc++.h>
const int N = 1001;
using namespace std;

int n;
int num[N][N] = {0};
int dp[N] = {0};

void readin(){
	for(int i = 1; i <= n - 1; i++){
		for (int j = i + 1; j <= n; j++) cin >> num[i][j];               
	}
}
int deal_two(){
	dp[1] = 0;
	dp[2] = num[1][2];
	
	for(int i = 3 ; i <= n ; i++){
		dp[i] = num[1][i];
		for(int j = 2 ; j <= n ; j++){
			dp[i] = min(dp[i] , dp[j] + num[j][i]);
		}
	}
	return dp[n];
}

int main(){
	cout << "请输入出租站个数：\n";
	cin >> n;
	readin()
	cout << "暴力：\n"; 
	cout << deal_one();
	cout << "\nDP：\n";
	cout << deal_two();
} 

本文地址：https://blog.csdn.net/qq_31747473/article/details/109234532