HDOJ 2084 수 탑 (전형 적 인 동적 계획 문제)

동적 계획 은 용도 가 매우 넓 은 문제 해결 방법 으로 그 자체 가 특정한 알고리즘 이 아니 라 사상, 수단 이다.
동적 계획 은 공간 을 희생 하고 시간 을 바 꾸 는 사상 이 라 고 할 수 있다.

#include
using namespace std;

int a[101][101],dp[101][101];//  a         、  dp[i][j]   （i,j）           （   （i,j）     ））
int main(){
    int t,n,i,j;
    scanf("%d",&t);
    while(t--){
          scanf("%d",&n);
          for(i=1;i<=n;i++)//           
              for(j=1;j<=i;j++)
                  scanf("%d",&a[i][j]);
          
          for(i=1;i<=n;i++)//dp[n][i]  a[n][i]   
              dp[n][i]=a[n][i];
              
          for(i=n-1;i>=1;i--)//             
              for(j=i;j>=1;j--)
                  dp[i][j]=a[i][j]+(dp[i+1][j]>dp[i+1][j+1]?dp[i+1][j]:dp[i+1][j+1]);//     dp[i+1][j]、dp[i+1][j+1]       
          printf("%d
",dp[1][1]);      
                 
    }
    return 0;
}