poj 1163 The Triangle【dp】

POJ3176과 거의 똑같아요.
AC 코드:

#include<stdio.h>

int dp[102][102];

inline int max(int a,int b){return a>b?a:b;}

int main()
{
    int n,i,j;

    scanf("%d",&n);

	//  
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&dp[i][j]);

	//dp
    for(i=n-1;i>=1;i--)
        for(j=1;j<=i;j++)
            dp[i][j]=max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i+1][j+1]);

    printf("%d
",dp[1][1]);

    return 0;
}

돌려서 괜찮게 쓴 스티커.
질문 설명: 숫자 삼각형을 입력하십시오
                                   7                                 3   8                                8  1   0                              2  7   4   4                           4   5   2   6   5
                            (Figure 1)
Figure 1과 같이 위에 있는 숫자 삼각형에서 맨 위에서 맨 끝까지의 경로를 찾아 경로에 지나는 숫자의 합을 최대로 한다.경로의 한 걸음 한 걸음은 모두 왼쪽 아래나 오른쪽 아래로 갈 수 있다.최상의 합만 요구하면 되고 출력 경로는 필요 없다.
문제 풀이 사고방식: 알고리즘 1. 귀속 사상
f(i,j)를 삼각형 위에서 점(i,j)에서 출발하여 아래로 내려가는 가장 긴 경로로 설정하면 f(i,j)=max(f(i1,j), f(i1,j1)가 출력할 것은 f(0,0) 즉 맨 위에서 출발하는 가장 긴 경로이다.
D(r, j)로 r행의 j번째 숫자를 나타내고, MaxSum(r, j)로 r행의 j번째 숫자의 끝을 나타내는 각 경로에서 숫자의 합이 가장 큰 경로의 숫자의 합을 나타내면 본 문제는 MaxSum(0,0)을 요구하는 것이다.(행 번호와 행 내 숫자 번호가 0부터 시작된다고 가정합니다.)전형적인 동태적 기획 문제.어떤 D(r, j)에서 출발하면 분명히 다음 단계는 D(r 1, j) 또는 D(r 1, j 1)만 갈 수 있기 때문에 N 줄의 삼각형에 대해 if(r==N-1)MaxSum(r, j)=D(N-1, j)elseMaxSum(r, j)=Max(r, j)=Max(r 1, j),MaxSum(r 1,j 1) ) D(r,j);
코드는 다음과 같습니다.
#include #define MAX 101 int triangle[MAX][MAX]; int n; int longestPath(int i, int j); void main(){ 　int i,j; 　cin >>n; 　for(i=0;i> triangle[i][j]; 　cout <왜 시간 초과가 됐죠?
답: 만약에 규칙을 적용하는 방법으로 모든 경로를 깊이 있게 훑어보고 대량의 중복 계산이 존재한다면 시간 복잡도는 2n이고 n=100에 대해서는 시간을 초과할 것이다.
가능한 개선 사상: 아래에서 위로 계산하면 모든 점에 대해 아래에서 오는 경로와 가장 큰 경로의 합만 보류하면 된다.그 위에 있는 점은 그 길로 오는 가장 큰 길과, 그 길로 오는 길에만 관심이 없기 때문이다.문제: 몇 가지 해법이 있습니까?스토리지 오버헤드 측면에서 분석 2?00?00개 izeof (int) 100개 izeof (int) 100개 izeof (int)
해법 1. MaxSum(r, j)을 계산할 때마다 저장하면 o(n2) 시간에 계산을 완성할 수 있다.삼각형의 숫자 총수가 n(n1)/2이기 때문에 이때 필요한 저장 공간은 int D[100][100];//삼각형의 숫자 int Sum[100][100];//저장각 MaxSum(r, j) 저장

해법 2.
매 MaxSum(r, j)을 2차원 수조로 저장할 필요가 없다. 밑줄에서 위로 밀어내면 1차원 수조Sum[100]만 저장하면 된다. 즉, 한 줄의 MaxSum 값만 저장하면 된다.비해법의 개선점은 공간을 절약하고 시간의 복잡도가 변하지 않는다는 데 있다.

해법 3.
2차원 그룹 D[100][100]를 사용하지 않고 숫자를 저장할 수 있습니까?사고방식: 거꾸로 생각하다.앞의 사고방식은 밑에서 위로 맥스섬(0,0)을 최종적으로 계산하는 것이다.만약 위에서 아래로 계산하면 최종적으로 매 맥스썸(N-1, j)을 계산한 다음에 가장 큰 맥스썸(N-1, j)을 취하는 것이 답이 아니겠는가?이때 추이 공식은if(r=0)MaxSum(r,j)=D[0][0]이다.                else                  MaxSum(r,j) = Max(MaxSum(r-1,j-1), MaxSum(r-1,j)) D[r][j]; 이중 순환 형식: for(r=0;r < N;r) for(j=0;j 해법 4:
즉, 본인이 집행한 알고리즘은 해법 3에서'위에서 아래로'의 사상을 바탕으로 한 숫자를 입력한 후에 임시로 저장한 다음에sum[i]로 이 곳의 최대 경로와 수를 저장한다. 입력한 숫자 삼각형은 1을 공차로 하는 등차수열로 그 변수 간의 친밀한 관계를 충분히 이용하기 때문에 성공적으로 실현하는 것은 어렵지 않다.구체적인 알고리즘은 다음과 같다.
#include using namespace std; int main(){    int sum[5051]={0};//데이터를 저장하는 수조,sum=(n^2+n)/2max(sum)=5050(n==100)intn,r,j,num,i=1,max=0;//r표 변화의 행수,cin>>n;//입력 데이터 줄 수 for(r=1;r<=n;r++) {for(j=1;j<=r;j++,i+) {scanf('%d', &num);//삼각형 데이터 입력 if(j=1) {sum[i]=num+sum [i-r+1],continue;}//입력한 줄의 첫 번째 수if(j=r)sum[i]=num+sum[i-r];//입력한 것은 줄마다 마지막 수인elsesum[i]=(sum[i-r]>sum[i-r+1]?sum[i-r]:sum[i-r+1])+num;//입력한 것이 중간수일 때}/*for(j=1;jmax)max=sum[j]; cout<소감: 이 문제를 풀면서 저는 알고리즘의 한계에서 벗어나 사고가 한층 더 향상되었습니다. 전에 비슷한 문제를 만났는데 처음에 사고의 한계를 받아서 검색을 하거나 그림과 관련된 여러 가지 경험을 통해 해결할 수 있는 문제가 있었는데 지금은 몇 십 줄의 코드만 있으면 해결될 줄 몰랐습니다."법칙은 왕왕 독한 눈을 가진 사람의 뇌에 장악된다!"그리하여 이런 한마디로 결말이 났다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj 1163 The Triangle【dp】

좋은 웹페이지 즐겨찾기