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


ระดับความยาก กลาง
ถามบ่อยใน ซิทริกซ์ เดอชอว์ Directi Expedia
การเขียนโปรแกรมแบบไดนามิก คณิตศาสตร์

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

ตัวอย่าง  

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

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

คำอธิบาย

ผลรวมสูงสุดที่สามารถทำได้โดยการเลื่อนจากบนลงล่างคือ 15 ซึ่งสามารถทำได้จากขั้นตอนต่อไปนี้: 1 -> 2 -> 12 ซึ่งสามารถเข้าใจได้ดีขึ้นจากภาพด้านบน

เข้าใกล้  

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

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

ดูสิ่งนี้ด้วย
องค์ประกอบที่อยู่ติดกันที่แตกต่างกันในอาร์เรย์

เรากำหนดกรณีฐานโดยเติม DP [0] [0] ด้วยเซลล์ของอาร์เรย์อินพุตเริ่มต้น เพราะเราไม่สามารถเข้าถึงเซลล์นี้จากเซลล์อื่นได้และนี่คือจุดเริ่มต้น หลังจากนี้ไปที่แถวที่สอง ที่นี่เรามีตัวเลือกเดียวสำหรับทั้งสองเซลล์ และตัวเลือกคือการเลือกเซลล์จุดยอดบนสุด จากนั้นหลังจากแถวนี้สำหรับเซลล์ทั้งหมดเราต้องตัดสินใจว่าจะเลือกเซลล์ใดเป็นเซลล์ต่อหรือเซลล์ที่อยู่ทางซ้ายของเซลล์ปัจจุบัน หลังจากเสร็จสิ้นเราจะนำค่าสูงสุดที่จัดเก็บไว้ที่แถวสุดท้ายของตาราง 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 ใหม่