动态规划租用游艇问题

---

---

租用游艇动态规划解决

长江俱乐部在长江设置了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;
}

运行截图