数塔取数问你——动态规划

数塔取数问题

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。 
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

该三角形第n层有n个数字，例如：

第一层有一个数字：5

第二层有两个数字：8 4

第三层有三个数字：3 6 9

第四层有四个数字：7 2 9 5

最优方案是：5 + 8 + 6 + 9 = 28

注意:上面应该是排列成一个三角形的样子不是竖向对应的，排版问题没有显示成三角形。

状态定义: F_i，j是第i行j列项最大取数和，求第n行F_n，m（0 < m < n）中最大值。

状态转移方程：F_i，j = max{F_i-1,j-1,F_i-1,j}+A_i,j

<sub>package DB;


import java.util.Scanner;


public class Demo1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n][n];
a[0][0] = sc.nextInt();
long max = 0;

for(int i=1;i<n;i++)
{
for(int j = 0;j <= i;j++)
{
int num = sc.nextInt();
if(j==0)
{
a[i][j] = a[i-1][j] + num;

}
else
{
a[i][j] = Math.max(a[i-1][j],a[i-1][j-1])+num;

}
max = Math.max(a[i][j],max);

}
}
System.out.println(max);

}

}</sub>

_{两种思考角度，一部分是从上到下一共是N层，每i层中也要进行i次比较，比较的时候要从下往上进行考虑，如果是第一列的话，那么只有一种情况，如果是其他情况的话，就会有两种情况，需要讨论，难度在于对于问题的分析与归纳，是思想，而不是代码的实现}