右三角数のパスの最大合計


難易度 ミディアム
よく聞かれる Citrix社 DEショウ ディレクティ エクスペディア
動的計画法 数学

「右数の三角形のパスの最大合計」という問題は、いくつかが与えられていることを示しています 整数 右三角数の形で。 上から始めて、そのすぐ下のセルまたはその右側のXNUMXつの場所にのみ移動するように、ベースに向かって移動した場合に達成できる最大の合計を見つけます。

右三角数のパスの最大合計

3 // Number of rows in the right number triangle
1
3 2
4 10 12
15

説明

上から下に移動することで達成できる最大合計は15です。これは次の手順で達成できます:1-> 2-> 12。上の画像からよりよく理解できます。

アプローチ

この問題に類似した他の問題がすでにいくつかあります。 私たちは問題を解決して見つけました , 最小 三角形の合計パス。 この問題は、これらの問題のわずかなバリエーションです。 したがって、ムーブメントに課せられる条件は、現在のセルのすぐ下またはすぐ右に移動できることです。 そして、あなたは一番上の頂点からである一番上から始めます。 次に、底に到達します。

XNUMXつの方法は使用することです 再帰。 インデックスを引数として取り、そのセルから達成できる最大値を見つける関数を作成します。 このようにして、再帰的に答えを見つけます。 しかし、これは問題に時間を要し、確実に制限時間を超える結果になります。 したがって、問題を効率的に解決するために。 これらの再帰呼び出しの結果を記憶することもできます。 または使用する 動的計画法 これを解決するために。 最初に小さなサブ問題の結果を計算し、次にそれらの結果を組み合わせて元の問題の答えを見つけるボトムアップアプローチについて説明します。

基本ケースを、DP [0] [0]を初期入力配列のセルで埋めることとして定義します。 他のセルからこのセルに到達することはできず、これが始まりだからです。 この後、XNUMX行目に移動します。 ここでは、両方のセルにXNUMXつのオプションがあります。 オプションは、一番上の頂点セルを選択することです。 次に、この行の後で、すべてのセルについて、どのセルを選択するかを決定する必要があります。これは、ちょうどセルまたは現在のセルのすぐ左側にあるセルのいずれかです。 これがすべて行われた後、dpテーブルの最後の行に格納されている最大値を取得します。

コード

右三角数のパスの最大合計を見つけるためのC ++コード

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

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}
3
1
3 2
4 10 12
15

右三角数のパスの最大合計を見つけるJavaコード

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      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();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

複雑さの分析

時間の複雑さ

O(N ^ 2)、 ここで、Nは三角形の行数を表します。 それが最後の行にある要素の数だからです。

スペースの複雑さ

O(1)、 DPテーブルに同じ入力配列を使用しているためです。 したがって、新しいDPアレイを作成するためのスペースを取らなかったため、スペースの複雑さは一定です。