피라미드 문제(동적 기획)

귀속

#include
#include

using namespace std;
int n,a[1003][1003] = {0};
bool b[1003][1003];
int opt(int i,int j){
    if(i == n)
        return a[n][j];
    if(!b[i][j]){
        a[i][j] = max(opt(i+1,j),opt(i+1,j+1)) + a[i][j];
        b[i][j] = true;
    }
    return a[i][j];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j =1;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    printf("%d",opt(1,1));
}

비귀속(동적 기획)

/*
[[0,0,0,0,7,0,0,0],
 [0,0,0,3,0,8,0,0],
 [0,0,8,0,1,0,1,0],
 [0,2,0,7,0,4,0,0],
 [4,0,5,0,2,0,6,5]]
 */

 #include
 #include
 using namespace std;
 int r,a[1002][1002],F[1002][1002];
 int main(){
    scanf("%d",&r);
    for(int i = 1;i<=r;i++)
        for(int j =1;j<=i;j++){
            scanf("%d",&a[i][j]);
            F[i][j] = a[i][j];
        }
    for(int i =r-1;i>0;i--)
        for(int j=1;j<=i;j++){
            F[i][j]+=max(F[i+1][j],F[i+1][j+1]);
        }
    printf("%d",F[1][1]);


 }