51nod -- 1002 数塔取数问题（一级算法题）

1002 数塔取数问题

---

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注 一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。 每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

5 8 4 3 6 9 7 2 9 5

例子中的最优方案是：5 + 8 + 6 + 9 = 28 Input 第1行：N，N为数塔的高度。(2 <= N <= 500) 第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数……第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。 Output 输出最大值 Input示例 4 5 8 4 3 6 9 7 2 9 5 Output示例 28

---

题解思路

---

/* * 本题是经典的动态规划问题： * 状态：d[i][j]表示从(i,j)出发，能得到的最大和。包括(i,j) * 那么原问题便转化成了求d[0][0] * 从(i,j)出发可以向下走(i+1,j),也可以向右下走(i+1,j+1), * 然后问题就变成了从(i+1,j)或者从(i+1,j+1)出发的最大和 * 于是状态转移方程为：d[i][j] = max(d[i+1][j], d[i+1][j+1]) + a[i][j] */

---

代码

---

import java.util.Scanner; public class Main{ static int n; static int[][] arr = null; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); //init arr = new int[n][n]; //input for(int i=0; i<n; ++i) for(int j=0; j<=i; ++j) arr[i][j] = sc.nextInt(); //precess //递归 int result = solve_one(0,0); System.out.println(result); //递推 int result_two = solve_two(); System.out.println(result_two); //记忆话搜索 //d[i][j]记录每次计算过的值，若计算过，就直接用 int[][] d = new int[n][n]; //init for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) d[i][j] = -1; int result_three = solve_three(0,0,d); System.out.println(result_three); } //递归 public static int solve_one(int i, int j){ if(i == n) return 0; else return Math.max(solve_one(i+1,j), solve_one(i+1, j+1)) + arr[i][j]; } //递推 public static int solve_two(){ int[][] dp = new int[n][n]; //这里也可以用一个一维数组 for(int i=0; i<n; ++i) dp[n-1][i] = arr[n-1][i]; for(int i=n-2; i>-1; --i) for(int j=0; j<=i; ++j) dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j+1]) + arr[i][j]; return dp[0][0]; } //记忆话搜索 public static int solve_three(int i, int j, int[][] d){ if(i == n) return 0; if(d[i][j] > 0) return d[i][j]; return d[i][j] = arr[i][j] + Math.max(solve_three(i+1, j, d), solve_three(i+1, j+1, d)); } }