เส้นทางผลรวมขั้นต่ำในรูปสามเหลี่ยม


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แอปเปิล บลูมเบิร์ก
แถว การเขียนโปรแกรมแบบไดนามิก

คำชี้แจงปัญหา

ปัญหา“ เส้นทางผลรวมขั้นต่ำในสามเหลี่ยม” ระบุว่าคุณได้รับลำดับในรูปสามเหลี่ยมของจำนวนเต็ม ตอนนี้เริ่มจากแถวบนสุดเท่าไหร่ผลรวมขั้นต่ำที่คุณสามารถทำได้เมื่อถึงแถวล่าง

ตัวอย่าง

เส้นทางผลรวมขั้นต่ำในรูปสามเหลี่ยม

  1
 2 3
5 8 1
5

คำอธิบาย
คุณสามารถเลื่อนไปตามเส้นทางในลักษณะต่อไปนี้ 1-> 3-> 1 ดังนั้นผลรวมคือ 5 ถ้าเราจะไปด้วยวิธีโลภ เราจะได้ 2 แทนที่จะเป็น 3 ดังนั้นเราจึงได้เพียง 8 หรือ 11 ซึ่งมากกว่า 5

เข้าใกล้

แล้วเราจะแก้เส้นทางผลรวมขั้นต่ำในรูปสามเหลี่ยมได้อย่างไร? นอกจากนี้เรายังได้แก้ไขปัญหาที่คล้ายกันซึ่งเราต้องหาไฟล์ เส้นทางผลรวมสูงสุดในรูปสามเหลี่ยม. ในโพสต์ก่อนหน้านั้นเราได้พูดคุยกันไปแล้วว่าแนวทางการบังคับแบบเดรัจฉานสำหรับปัญหาเหล่านี้คือการสร้างเส้นทางทั้งหมด หลังจากการสร้างเส้นทางเหล่านี้เพียงแค่คำนวณผลรวมของแต่ละเส้นทางเหล่านี้และอัปเดตผลรวมขั้นต่ำ

ดังนั้นแทนที่จะแก้ปัญหานี้โดยใช้กำลังดุร้ายเราแก้ปัญหานี้ด้วย การเขียนโปรแกรมแบบไดนามิก. เนื่องจากวิธีการบังคับแบบเดรัจฉานนั้นไม่มีประสิทธิภาพสูง

ขั้นแรกเรากรอกคำตอบสำหรับเซลล์ในแถวสุดท้าย เรารู้ว่าผลรวมขั้นต่ำที่สามารถทำได้คือถ้าเราเริ่มจากเซลล์แถวล่างสุดก็คือตัวเลขนั่นเอง หลังจากนั้นเราย้ายไปที่แถวด้านบนแถวล่างสุด สำหรับแต่ละเซลล์ในแถวปัจจุบันเราสามารถเลือกค่า DP ของเซลล์ที่อยู่ติดกันในแถวด้านล่างได้ และกรอกค่าขั้นต่ำที่สามารถทำได้ วิธีนี้ทำให้เราไปในทิศทางที่สูงขึ้น เมื่อเราไปถึงแถวบนสุดเราก็จัดการกับปัญหาเรียบร้อยแล้ว

รหัส C ++ เพื่อค้นหาผลรวมของเส้นทางขั้นต่ำในรูปสามเหลี่ยม

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(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<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

โค้ด Java เพื่อค้นหาผลรวมพา ธ ขั้นต่ำในรูปสามเหลี่ยม

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(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 = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (N ^ 2)ในขณะที่เราย้ายข้ามแต่ละแถวและแต่ละคอลัมน์ ในกระบวนการนี้เราเดินทางไปยังแต่ละเซลล์ และเนื่องจากมีเซลล์ O (N ^ 2) อยู่ในรูปสามเหลี่ยมและการเปลี่ยน DP จึงใช้การดำเนินการ O (1) เท่านั้น ดังนั้นความซับซ้อนของเวลาจึงเป็นพหุนามด้วย

ความซับซ้อนของอวกาศ

O (N ^ 2) ตั้งแต่เราสร้างอาร์เรย์ 2D DP ดังนั้นความซับซ้อนของปริภูมิจึงเป็นพหุนามด้วย