poj 1163

这道题是一道简单的dp题，就是求从第一个数到底行中的某个数的路径数字之和最大值。这道题的子问题就是求到每一行的每一个数的路径的最大数字和。

设：t[i][j]储存第i行第j列的数字。

maxsum[i][j]储存到第i行第j列数字的路径的最大数字和。

dp方程是：

maxsum[i][j] = (maxsum[i - 1][j - 1] + t[i][j]) > (maxsum[i - 1][j] + t[i][j]) ? (maxsum[i - 1][j - 1] + t[i][j])
: (maxsum[i - 1][j] + t[i][j]);

ps：这道题在poj上提交AC，但是在百练是提交内存溢出。

import java.util.Scanner;

public class Main1163 {

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int[][] t = new int[n + 1][];
  int[][] maxsum = new int[n + 1][];
  for (int i = 1; i <= n; ++i) {
   t[i] = new int[i+1];
   maxsum[i] = new int[i+1];
   for (int j = 1; j <= i; ++j) {
    t[i][j] = sc.nextInt();
   }
  }
  for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= i; ++j) {
    if (i - 1 == 0)
     maxsum[1][1] = t[1][1];
    else if (j - 1 == 0)
     maxsum[i][j] = maxsum[i - 1][j] + t[i][j];
    else if (j > i - 1)
     maxsum[i][j] = maxsum[i - 1][j - 1] + t[i][j];
    else {
     maxsum[i][j] = (maxsum[i - 1][j - 1] + t[i][j]) > (maxsum[i - 1][j] + t[i][j]) ? (maxsum[i - 1][j - 1] + t[i][j])
       : (maxsum[i - 1][j] + t[i][j]);

    }
   }
  }
  int max = -1;
  for(int i = 1 ; i <= n ; ++i){
   if(maxsum[n][i] > max)
    max = maxsum[n][i];
  }
  System.out.println(max);

 }

}