学步园

这道题是一道简单的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;</p> <p>public class Main1163 {</p> <p> public static void main(String[] args) {<br /> Scanner sc = new Scanner(System.in);<br /> int n = sc.nextInt();<br /> int[][] t = new int[n + 1][];<br /> int[][] maxsum = new int[n + 1][];<br /> for (int i = 1; i <= n; ++i) {<br /> t[i] = new int[i+1];<br /> maxsum[i] = new int[i+1];<br /> for (int j = 1; j <= i; ++j) {<br /> t[i][j] = sc.nextInt();<br /> }<br /> }<br /> for (int i = 1; i <= n; ++i) {<br /> for (int j = 1; j <= i; ++j) {<br /> if (i - 1 == 0)<br /> maxsum[1][1] = t[1][1];<br /> else if (j - 1 == 0)<br /> maxsum[i][j] = maxsum[i - 1][j] + t[i][j];<br /> else if (j > i - 1)<br /> maxsum[i][j] = maxsum[i - 1][j - 1] + t[i][j];<br /> else {<br /> 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])<br /> : (maxsum[i - 1][j] + t[i][j]);</p> <p> }<br /> }<br /> }<br /> int max = -1;<br /> for(int i = 1 ; i <= n ; ++i){<br /> if(maxsum[n][i] > max)<br /> max = maxsum[n][i];<br /> }<br /> System.out.println(max);</p> <p> }</p> <p>}<br />