网站seo如何做sem优化是什么意思

题目链接：数塔（动态规划入门）

动态规划（dp），是算法中十分常用的一个技巧，而数塔通常作为入门级别的题目来解释

分析：

题目要求我们从顶向下找出一条结点数和最大的路径，但只需要最大路径的值。

每一步只能走到相邻的结点。然后我们自然就会想真的每一步都走一遍，然后比较结果大小

但是这样的效率显然是达不到要求的，然后再想办法做优化

既然自顶向下，那么我们可以再做一个一样的数组

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

假设从第二行第i个开始，加上 上一行的第i个或者第i-1个，哪个大就保存哪个的和

然后数塔就变成了

7

10 15

8   1   0

2   7   4   4

4   5   2   6   5

再下一行就是

  7

10 15

18   16   15

  2     7     4   4

  4     5     2   6   5

以此类推，最后将最后一行比较一下，看看哪个最大就是他了

下面AC代码：

import java.util.Scanner;
public class Main{private static Scanner scanner;public static void main(String[] args) {scanner = new Scanner(System.in);int n = scanner.nextInt();while (n-- > 0) {int line = scanner.nextInt();// 一共有几行// 定义不数组int[][] dp = new int[line][line];// 接收数组int t = 1;for (int i = 0; i < dp.length; i++) {for (int j = 0; j < t; j++) {dp[i][j] = scanner.nextInt();}t++;}for (int i = 1; i < dp.length; i++) {for (int j = 0; j < dp[i].length; j++) {if (j == 0) {dp[i][j] += dp[i - 1][j];} else {if (dp[i][j] + dp[i - 1][j - 1] > dp[i][j] + dp[i - 1][j]) {dp[i][j] += dp[i - 1][j - 1];} else {dp[i][j] += dp[i - 1][j];}}}}//比较最后一行int max = dp[line-1][0];//先设为第一个for (int i = 1; i < dp[line-1].length; i++) {if(dp[line-1][i]>max){max = dp[line-1][i];}}System.out.println(max);}}
}

不，懒惰的我不想最后还是要比较！

于是，有了另一种，就是从底向上的方法

思路其实差不多的，倒数第二行的数从j=0开始，加上他的下一行的第j或j+1个数

看看哪个大，然后将倒数第二行的第j个改为大的那个数加上本身

然后j++，一样的比较，完了以后，再上一行，再上一行。。。

OK，第一个就是答案！

下面是这种方法的AC代码：

import java.util.Scanner;public class Main{private static Scanner scanner;public static void main(String[] args) {scanner = new Scanner(System.in);int n = scanner.nextInt();while(n-->0){int line = scanner.nextInt();//一共有几行//定义不规则数组int [][]dp = new int[line][];for (int i = 0; i < dp.length; i++) {dp[i] = new int[i+1];}//接收数组for (int i = 0; i < dp.length; i++) {for (int j = 0; j < dp[i].length; j++) {dp[i][j] = scanner.nextInt();}}for (int i = line-2; i >= 0; i--) {for (int j = 0; j < dp[i].length; j++) {if(dp[i][j]+dp[i+1][j]>dp[i][j]+dp[i+1][j+1]){dp[i][j] += dp[i+1][j];}else {dp[i][j] += dp[i+1][j+1];}}}//打印数塔/*for (int i = 0; i < dp.length; i++) {for (int j = 0; j < dp[i].length; j++) {System.out.print(dp[i][j]+" ");}System.out.println();}*/System.out.println(dp[0][0]);}}
}