三角形中的最大路径总和  


难度级别 中等
经常问 弓箭 编码国家 GE医疗集团 PayU 尤伯杯 百会
动态编程

问题陈述  

问题“三角形中的最大路径总和”指出给了您一些整数。 这些整数以三角形的形式排列。 您从三角形的顶部开始,需要到达底部的行。 为此,您移至下一行中的相邻单元格。 因此,当您以定义的方式向下移动三角形时,可以达到的最大总和是多少?

使用案列  

三角形中的最大路径总和

  1
 2 3
5 8 1
12

说明
您可以按照以下方式简单地沿路径移动。 1-> 3-> 8,此路径将使您获得的最大总和为12。

途径  

那么,我们如何解决三角形中的最大路径总和? 到现在为止,我们对此类问题还是非常熟悉的。 每当我们遇到此类问题时。 暴力破解方法始终是首先生成所有可能的到达目的地的方法。 然后,通过计算每个路径的总和,继续更新最佳结果的答案。 但是这种方法效率极低,因为这种方法需要我们生成路径。 而且我们知道,路径生成是一项具有指数时间复杂度的任务,这并不好。

因此,要解决此问题,我们需要考虑另一种方法。 然后 动态编程 来救援。 因为不是生成路径,而是如果我们能以某种方式知道从一个单元格到达最底行所能达到的最大值。 这样,我们可以获取与其相邻但在其上方的行中的单元格的结果。 因此,我们使用DP解决较小的子问题。 然后结合这些子问题的结果,我们找到了原始问题的答案。

参见
段树

首先,我们为最后一行的单元格填写答案。 我们知道,如果我们从底行的单元格开始,则可以实现的最大和为数字本身。 之后,我们移至最底行上方的行。 对于当前行中的每个单元格,我们可以在其正下方的行中选择与其相邻的单元格的DP值。 这样,我们继续朝着向上的方向前进。 当我们到达第一行时,我们就解决了问题。

C ++代码在三角形中找到最大路径总和  

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int maximumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] > input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}

int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

Java代码查找三角形中的最大路径总和  

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] > input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++){
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();
      }
      int answer = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

复杂度分析  

时间复杂度

O(N ^ 2),当我们在每一行和每一列中移动时。 在此过程中,我们前往了每个牢房。 并且由于三角形中有O(N ^ 2)个像元,因此DP的过渡仅需O(1)运算。 因此,时间复杂度也是多项式。

参见
回文链表Leetcode解决方案

空间复杂度

O(N ^ 2) 因为我们创建了2D DP阵列。 因此,空间复杂度也是多项式。