DP:The Triangle
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 29626
Accepted: 17473
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)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
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5Sample Output
30#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int n;
int num[110][110];
int memo[110][110];
int dp(int i,int j){
int ret=0;
if(memo[i][j]!=-1) //
return memo[i][j];
if(i==1) // ， i = 1
return memo[i][j]=num[i][j];
if(i<1||j>n-i+1||j<1) //
return memo[i][j]=0;
return memo[i][j]=max(dp(i-1,j),dp(i-1,j+1))+num[i][j]; //
}
int main(){
int i,j;
while(cin>>n){
for(i=0;i<110;i++)
for(j=0;j<110;j++)
memo[i][j]=-1;
for(i=n;i>0;i--)
for(j=1;j<=n-i+1;j++)
scanf("%d",&num[i][j]);
dp(n,1);
cout<<memo[n][1]<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
