Arithmetic problem | The Triangle

제목은 다음과 같습니다.
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
(Figure 1)

3 : 8
8 : 1 : 0
2 : 7 : 4 : 4
4 : 5 : 2 : 6 : 5
Input:
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input:
Triangle

3 : 8
8 : 1 : 0
2 : 7 : 4 : 4
4 : 5 : 2 : 6 : 5
Sample Output: 30
문제 풀이 사고방식: 이 문제는 각 층이 하나의 구성 노선을 선택하여 최대 수치에 도달해야 하기 때문에 동적 기획으로 기존의 데이터 정보를 최대한 활용하여 계산하는 것이 좋은 선택이다.여기서 각 층은 하나의 상태로 점차적으로 점차적으로 증가하는 상태로 문제를 0-2층, 0-3층으로 분해한다...0-(n-1)층의 최대 노선 가치.n-2층의 데이터 이동을 통해 n-1층을 형성하고 n-3층->n-2층, n-4층->n-3층으로 계속 하분한다...주체적으로 보면 비교적 간단한 제목이다.
사고방식 코드는 다음과 같습니다.
int Method(int **n,int len)
{
    int res=0;
    for(int i=1;i<len;++i)
    {
        for(int p=0;p<=i;++p)
        {
            if(p==0) *((int*)n+len*i+p)+= //n[i][p]
            *((int*)n+len*(i-1)+p); //n[i-1][p]
            else if(p==i) *((int*)n+len*i+p)+=
                *((int*)n+len*(i-1)+(p-1)); //n[i-1][p-1]
            else *((int*)n+len*i+p)+=
            max(*((int*)n+len*(i-1)+(p-1)),
                *((int*)n+len*(i-1)+p));
        }
    }
    for(int i=0;i<len;++i)
        res=max(res,
                *((int*)n+len*(len-1)+i));//n[len-1][i]
    return res;
}

좋은 웹페이지 즐겨찾기