Pyramid Slide Down（4Kyu） - 图1

题目

Pyramids are amazing! Both in architectural and mathematical sense. If you have a computer, you can mess with pyramids even if you are not in Egypt at the time. For example, let’s consider the following problem. Imagine that you have a pyramid built of numbers, like this one here: /3/ \7\ 4
2 \4\ 6
8 5 \9\ 3 Here comes the task… Let’s say that the ‘slide down’ is the maximum sum of consecutive numbers from the top to the bottom of the pyramid. As you can see, the longest ‘slide down’ is 3 + 7 + 4 + 9 = 23 Your task is to write a function longestSlideDown (in ruby/crystal/julia: longest_slide_down) that takes a pyramid representation as argument and returns its’ largest ‘slide down’. 金字塔太神奇了！在建筑和数学意义上。如果你有电脑，即使你当时不在埃及，你也可以捣乱金字塔。例如，让我们考虑以下问题。想象一下你有一个由数字组成的金字塔，就像这里的这个： /3/ \7\ 4
2 \4\ 6
8 5 \9\ 3 任务来了。。。

假设“向下滑动”是从金字塔顶部到底部的连续数字的最大和。如你所见，最长的“滑下”是3+7+4+9=23

您的任务是编写一个longestsliddedown函数（在ruby/crystal/julia:longest\u slide\u down中），该函数以金字塔表示形式作为参数并返回其“最大”slide down。

例子

[[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]] => 23

原题链接

分析

从金字塔顶到底找出数字之和最大的路径，每次只能向左下或向右下走。经典的动态规划问题，这里只需要注意要从最底部向上寻找最大路径即可。

我的解法

  1. public class LongestSlideDown {
  3.     public static int longestSlideDown(int[][] pyramid) {
  4.         for (int i = pyramid.length-1; i >= 0; i--) {
  5.             int j = 0;
  6.             while (j<i){
  7.                 pyramid[i-1][j] =  pyramid[i-1][j] + (pyramid[i][j] > pyramid[i][j+1] ? pyramid[i][j]:pyramid[i][j+1]);
  8.                 j++;
  9.             }
  10.         }
  11.         return pyramid [0][0];
  12.     }
  13. }

参考解法

  1. public class LongestSlideDown {
  3.     public static int longestSlideDown(int[][] p) {
  5.         for (int i = p.length - 1; i >= 1; i--)
  6.           for (int j = 0; j < i; j++)            
  7.             p[i - 1][j] += Math.max(p[i][j], p[i][j + 1]);
  9.         return p[0][0];
  10.     }
  11. }

提升

  1. 动态规划就是将大问题分解成小问题，然后缓存小问题的结果，汇总起来就是大问题的结果了
  2. 具体操作如下