租用游艇动态规划解决
长江俱乐部在长江设置了n个游艇出租站1,2,…n，游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j)，设计一个算法，计算出从出租站1到出租站n所需要的最少租金。
测试用例：
3（站数）
515（第一站到其他相应各站的租金）
7（第二站到其他相应各站的租金）
输出： 12
分析：
本题是运用动态规划求解，动态规划总的思想就是从下到上，从底到顶。一开始需要打好数组的底子，后续的计算会根据底子逐步得出需要的结果。
有了这个想法，当时联想到了数字三角形的问题，数字三角形是一道典型的由下到上的动态规划问题。进而想到：想求min(1->n)，那我把min(1->n-1)求出来，加上r[n-1][n]得出一个数值,再和r[1][n]比较，取最小不就解决了吗？即：min=r[1][n-1]+r[n-1][n]>r[1][n]?r[1][n-1]+r[n-1][n]:r[1][n];
显然这是种错误的想法，错在：我误认为每次游艇从第一站出发后，经过n次停歇后，都会在第n-1站停下，然后从第n-1站出发到第n站。显然游艇可能在第k站停下，但不一定在第n-1站停下。
从第1站出发到第n站，游艇停几次不知道，在哪一站停也不知道，这就类似于矩阵相乘问题，究竟每次几个矩阵相乘不知道，从第k个矩阵分开，k等于多少也不知道。
1、动态规划解决必然用到存放子问题最优解的数组，r[i][j]代表从i站到j站的最少租金
2、数组打底工作分两步：（1）本题目中输入的价格是数组的底，表示从某一种到另一种不停留，直接到达的费用。（2）r[i][i]从i站出发，到达i站的费用，当然是0。
３、r[i][j]=r[i][k]+r[k][j],从i站到j站的最少租金=从i站到k站的最少租金+从k站到j站的最少租金。
**本题虽然和“矩阵连乘”、“石子合并”类似，但要注意不是K+1 **
代码：
#include<stdio.h>
int n; //n个出租站
int main(){
scanf("%d",&n);
int **r=new int*[n+1]; //多申请了一组空间，解决了下标i和第i个数值不同的问题
for(int i=0;i<n+1;i++){
r[i]=new int[n+1];
}
for(int i=1;i<n+1;i++){ //有选择性地输入，用不着的都空着
for(int j=i+1;j<n+1;j++)
scanf("%d",&r[i][j]);
}
for(int i=1;i<n+1;i++) //例如：第3站到第三站的价钱为0（数组打底，首先从某一站走到它自己）
r[i][i]=0;
for(int l=2;l<=n;l++){ //从两个出租站开始，逐步计算每多个出租站之间的最优解
for(int i=1;i<=n-l+1;i++){
int j=i+l-1;
for(int k=i+1;k<j;k++){
int temp=r[i][k]+r[k][j];
if(temp<r[i][j])
r[i][j]=temp;
}
}
}
printf("%d",r[1][n]);
return 0;
}
