TopCoder SRM256 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。

次のような数字の並びを考える。

1	0	3	4	1
4	5	8	15	20
1	10	23	46	81
0	11	44	113	240
3	14	69	226	579

一番上の行と、一番左の列を除いて、各数は左、上、左上の3つの値の和になっている。1行目を表すrow[]と、1列目を表すcol[]が与えられたときに、最も右下の値の計算結果を返せ。上の例ではrow[] = {1,0,3,4,1}、 col[] = {1,4,1,0,3}という意味になる。また、row[]とcol[]の要素数は常に一致するものとする。

私の解答はこちら。

public class GridGenerator {

 public int generate(int[] row, int[] col) {
  int[][] grid = new int[row.length][col.length];
  for( int i=0 ; i<row.length ; i++ ){
   grid[i][0] = row[i];
   grid[0][i] = col[i];
  }
  for( int i=1 ; i<row.length ; i++ ){
   for( int j=1 ; j<col.length ; j++ ){
    grid[i][j] = grid[i][j-1] + grid[i-1][j-1] + grid[i-1][j];
   }
  }
  return grid[row.length-1][col.length-1];
 }

}

row[]、col[]を二次元配列の1行目、1列目に設定してしまえば、簡単な問題に落とし込めると思います。