租用游艇问题（动态规划）

问题描述：

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

输入：

第一行一个正整数n表示有n个游艇出租站。接下来n-1行时r(i, j)

输出：

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

样例输入：

3
5 15
7

样例输出：

12

code:

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e3+7;
const int INF = 0x3f3f3f3f;

int r[N][N];
int dp[N][N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            cin >> r[i][j];
            dp[i][j] = r[i][j];
        }
    }
    
    for(int i = 1; i <= n; i++)
        dp[i][i] = 0;
    for(int s = 2; s <= n; s++)
    {
        for(int i = 1; i <= n-s+1; i++)
        {
            int j = i + s - 1;
            for(int k = i; k <= j-1; k++)
            {
//				dp[i][j] = min(dp[i][j], r[i][k] + r[k][j]);
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }

    cout << dp[1][n] << endl;


    return 0;
}