#UVa：485－Pascal’s Triangle of Death

大數加法+DP建表得解。

P.S. 須注意這題不用全部的數字記下來，不然記憶體會炸掉。只要記住一行，輸出完後再從該行推出下一行，然後下一行的資料蓋掉原本那行的資料，這樣一行一行運算完就可以了。

C++(0.292)

/*******************************************************/
/* UVa 485 Pascal's Triangle of Death                  */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/02/02                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int dp[1500][150] = {0};

int main(){
  dp[0][0] = 1;
  int row = 1, digit;
  bool exit = 0;
  do{
    for( int i = row-2 ; i > 0 ; i-- ){
      for( int j = 0 ; j < 150 ; j++ ){
        dp[i][j] += dp[i-1][j];
        dp[i][j+1] += dp[i][j]/10;
        dp[i][j] %= 10;
      }
    }
    for( int i = 0 ; i < row ; i++ ){
      for( digit = 149 ; digit >= 0 ; digit-- )
        if( dp[i][digit] ) break;
      if( digit >= 60 ) exit = 1;

      for( ; digit >= 0 ; digit-- )
        printf( "%d", dp[i][digit] );

      if( i != row-1 ) printf( " " );
      else printf( "\n" );
    }
    dp[row++][0] = 1;
  } while( !exit );
  return 0;
}