동적 계획 의 용선 문제

동적 계획 의 용선 문제
[문제] 장강 요트 클럽 은 장강 에 n 개의 요트 임대 소 를 설치 했다. 1, 2,..., n.관광객 들 은 이들 요트 대여 소 에서 요트 를 빌 리 고 하류의 어떤 요트 대여 소 에서 도 요트 를 돌려 줄 수 있다.요트 대여 소 i 에서 요트 대여 소 j 사이 의 임대 료 는 r (i, j), 1 < = i < j < = n 이다.요트 대여 소 1 부터 요트 대여 소 n 까지 필요 한 최소 임대 료 를 계산 하 는 알고리즘 을 시험 적 으로 설계 하 다.
[분석] p [i] [j] 가 i 시 부터 배 를 빌 리 기 시작 하고 j 시 까지 배 를 돌려 주 는 최소 비용 (최 우수 치) 이 라 고 가정 하면 p [i] [j + 1] = min {p [i] [j] + m [j + 1], m [i] [j] 는 입력 한 데 이 터 를 위해 i 번 째 용선 점 에서 j 번 째 환 선 점 까지 의 직접 비용 을 나타 낸다.이 식 에서 우 리 는 두 값 의 크기 를 비교 하면 현재 환 선 점 과 제 i 의 용선 점 간 의 최소 비용 을 얻 을 수 있 음 이 분명 하 다.따라서 최종 결 과 는 p [0] [n - 1] (아래 표 0 부터 기록) 이다.
[프로그램 실행 시 뮬 레이 션]

       ：
                  4
            5 14 23
               5 12
                  8     
          （ m[i][j]）          
       \   
                0   1   2   3
            0   0   5   14  23
            1   0   0   5   12
            2   0   0   0   8
            3   0   0   0   0
p[i][j]：
       \    
                0   1   2   3
            0   0   5   10  17
            1   0   0   5   12
            2   0   0   0   8
            3   0   0   0   0

【 프로그램 】

    #include
    using namespace std;

    int min(int a, int b) {
        return a < b ? a : b;
    }

    int main() {
        int n;
        cin>>n;
        //m[i][j]      
        int **m = new int*[n];
        for (int i = 0; i < n; i++) {
            m[i] = new int[n];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                m[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                cin>>m[i][j];
            }
        }
        //p[i][j]   i   j      
        int **p = new int*[n];
        for (int i = 0; i < n; i++) {
            p[i] = new int[n];
        } 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                p[i][j] = 0;
            }
        }

        for (int i = 0; i < n; i++) {
            int minNum = m[0][i];
            for (int j = 0; j < i; j++) {
                minNum = min(minNum, p[0][j] + m[j][i]);

            }
            p[0][i] = minNum;
        }

        cout<
0][n - 1];
    }