java算法

1.题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 

      3   8 

    8   1   0 

  2   7   4   4 

4   5   2   6   5 

在上面的样例中,从 7 \to 3 \to 8 \to 7 \to 57→3→8→7→5 的路径产生了最大

输入输出样例

输入 #1

573 88 1 02 7 4 44 5 2 6 5

输出 #1

30

import java.util.Scanner;public class Main4 {     public static void main(String[] args) {   Scanner scanner = new Scanner(System.in);   int n = scanner.nextInt();   int[][] arr = new int[n][n];   int[][] count = new int[n][n];   for (int i = 0; i < n; i++) { for (int j = 0; j < i + 1; j++) {      arr[i][j] = scanner.nextInt(); }   }   count[0][0] = arr[0][0];   if(n == 1){ System.out.println(count[0][0]); return;   }   count[1][0] = arr[1][0]+arr[0][0];   count[1][1] = arr[1][1]+arr[0][0];   if(n == 2){ System.out.println(Math.max(count[0][0]+count[1][0],count[1][1])); return;   }   int sum = Integer.MIN_VALUE;   for (int i = 2; i < n; i++) { for (int j = 0; j <= i; j++) {      if(j == 0)    count[i][j] = count[i-1][j]+arr[i][j];      else if (j == i)    count[i][j] = count[i-1][j-1]+arr[i][j];      else {    count[i][j] = Math.max(arr[i][j]+count[i-1][j],arr[i][j]+count[i-1][j-1]);      } }   }   for (int i = 0; i < n; i++) { sum = Math.max(sum,count[n-1][i]);   }   System.out.println(sum);     }}

发现这个MLE里面的例子有上万行，我的....

优化后的代码

其实可以从下往上走，在走的时候就已经做了判断大小，不需要之前走完还有继续比较

import java.util.Scanner; public class Main {   public static void main(String[] args) {    // TODO 自动生成的方法存根    Scanner sc = new Scanner(System.in);    int n = sc.nextInt();// 数组的行列数    int[][] num = new int[n][n];    for (int i = 0; i < n; i++) {// 输入数组      for (int j = 0; j < i + 1; j++) { num[i][j] = sc.nextInt();      }    }    System.out.println(dpd(num));  }   public static int dpd(int[][] num) {    int row = num.length;// 定义行数    int line = num[row - 1].length;// 定义列数    int[][] dp = new int[row][line];// 定义dp数组    for (int i = 0; i = 0; i--) {// 从最后一行向前走 所以i从倒数第二行开始      for (int j = 0; j <= i; j++) { dp[i][j] = num[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);      }    }    return dp[0][0];  }}

2.题目

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入 #1

389 207 155 300 299 170 158 65

输出 #1

6

2

import java.util.Scanner;public class te {     //动态规划，创建特殊数组     static int[] len, height, count;     static int max1, max2;     public static void dio(int k){   for (int i = 0; i < k; i++) { len[i] = 1; count[i] = 1; //每一次都与前面的数遍历，只取最大值 for (int j = 0; j < i; j++) {      if(height[i] <= height[j]){    len[i] = Math.max(len[i], len[j]+1);      }else{    count[i] = Math.max(count[i], count[j]+1);      } }//389 207 155 300 299 170 158 65 max1 = Math.max(max1, len[i]); max2 = Math.max(max2, count[i]);   }     }     public static void main(String[] args) {   Scanner sc = new Scanner(System.in);   String arr = sc.nextLine();   String[] a = arr.split(" ");   int n = a.length;   len = new int[n];   count = new int[n];   height = new int[n];   for (int i = 0; i < n; i++) { height[i] = Integer.parseInt(a[i]);   }   dio(n);   System.out.println(max1);   System.out.println(max2);     }}