DP 디지털 삼각형(POJ1163)

1731 단어 dp
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위의 숫자 삼각형에서 맨 위에서 끝까지 가는 경로를 찾아 경로에 지나는 숫자의 합이 가장 크다.
경로의 한 걸음 한 걸음은 왼쪽 아래나 오른쪽 아래로만 갈 수 있다.이 최대 화합만 요구하면 되며 구체적인 경로를 제시할 필요가 없다.
삼각형의 줄 수는 1보다 크고 100보다 작으며 숫자는 0-99이다
"사람마다 나를 위해"점차적 귀환 절차
a(i, j): i행 j번째 숫자(i, j는 1부터 계산)
dp(i, j): a(i, j) 끝의 각 경로에서 가장 좋은 경로의 숫자의 합.
질문: dp(1,1) 구하기
D(r, j)가 출발하면 다음 단계는 D(r+1, j) 또는 D(r+1, j+1)만 갈 수 있다.그러므로 N 행의 삼각형에 대해 다음을 수행합니다.
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j) 
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    int t,n;
    int dp[105][105];
    int a[105][105];
    //scanf("%d",&t);
    while(scanf("%d",&n)!=EOF)
    {

        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= i ; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i = n ; i >= 1 ; i--)
        {
            for(int j = 1 ; j <= i ; j++)
            {
                if(i==n)dp[i][j]=a[i][j];
                else
                {
                    dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
                }
            }
        }
//        for(int i = 1 ; i <= n ; i++)
//        {
//            for(int j = 1 ; j <= i ; j++)
//            {
//                printf("%d ",dp[i][j]);
//            }
//            printf("
");
//        }
        printf("%d
",dp[1][1]);
    }
    return 0;
}

/*
Auther:LIUYAN
2015.11.30
     (POJ1163)
100
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/
Docker1.3판 boot2 docker+fig 시작
Docker 컨테이너의 행렬

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage