题目：长江港口出租游艇，有1,2….n个出租站点，游客可在这个某出租站点租游艇，然后在下游任一出租站点归还游艇。游艇出租站i到j的出租费用为r(i,j);1<=j<j<=n,计算港口1到n的最小费用。
Input
第 1 行中有 1 个正整数 n（n<=200） ，表示有 n个游艇出租站。
接下来的n-1 行是r(i,j), r(i,j)为整数，1 ≤ i < j ≤ n。
Output
输出从游艇出租站1到游艇出租站n所需的最少租金。
Sample Input
3
5 15
7
Sample Output
12
直接保存起点到每个点的最少租金
分析：假设出租站点1到出租站点n的最短费用不是为1到n的直通费用，就是说最短费用是在1到n中间，至少在某一个出租点还了游艇，然后又继续租游艇到站点n，所以最少费用满足min=min(Min(i,j)+Min(j,n)),1<j<n;所以此题满足动态规划的最优子结构性质。当我们求出租站1到出租站n的最少费用时候，我们需要知道出租站2到出租站n的最少费用，并且需要知道3->n的最少费用，当我们求出租站2到出租站n的最少费用的时候，又需要知道出租站3到出租站n的最少费用，所以此题也满足动态规划的第二个性质：子问题重叠！
自底向上
s[i][j]存的从i到j的最少租金1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include<bits/stdc++.h>
#define MAX 100
using namespace std;
int d[MAX][MAX],m[MAX][MAX],s[MAX][MAX];
void print(int i,int j){
if(s[i][j]==0) {
cout<<j<<"--";
return;
}
print(i,s[i][j]);
print(s[i][j],j);
}
int main(){
int n;
cin>>n;
memset(s,0,sizeof(s));
memset(d,0,sizeof(d));
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
{
cin>>d[i][j];
m[i][j]=d[i][j];
}
}
for(int d=3;d<=n;d++){
for(int i=1;i<=n-d+1;i++){
int j=i+d-1;
for(int k=i+1;k<j;k++){
if(m[i][k]+m[k][j]<m[i][j])
{
s[i][j]=k;
m[i][j]=m[i][k]+m[k][j];
}
}
}
}
cout<<1;
print(1,n);
cout<<"cost:"<<m[1][n]<<endl;
}
自顶向下的方法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/ 港口最少费用.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <stdio.h>
#include <limits.h> //有个表示int类型最大值的宏在这个头文件里面
int FindMinest(int (*p)[10], int (*m)[10], int k, int n);
int Min(int a, int b);
int main()
{
int n;
int p[10][10] = { 0 }; //保存出租站之间的直通费用
int m[10][10] = { 0 }; //保存出租站之间的最短费用
scanf_s("%d", &n);
for (int i = 0; i < n-1; ++i) {
for (int j = i+1; j < n; ++j) {
scanf_s("%d", &p[i][j]); //输入出租站之间的直通出租费用
}
}
int min = FindMinest(p, m, 0, n-1);
printf("%d", min);
return 0;
}
//自顶向下的方法
int FindMinest(int(*p)[10], int(*m)[10], int k, int n) {//这个函数的作用就是找到港口K到港口n的最小费用
int min = INT_MAX;
if (k == n) {
return 0;
}
if (m[k][n] > 0) {
return m[k][n];
}
for (int i = k + 1; i <= n; ++i) {
min = Min(min, p[k][i] + FindMinest(p, m, i, n));
}
m[k][n] = min;
return min;
}
int Min(int a, int b) {
return a < b ? a : b;
}
1 | #include <iostream> |