요트 임대 문제 (동적 계획)

질문 설명:
창 장 요트 클럽 은 창 장 에 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 
#include 
#include 

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;
}