Ελάχιστη διαδρομή αθροίσματος σε ένα τρίγωνο


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα μήλο Bloomberg
Παράταξη Δυναμικός προγραμματισμός

Δήλωση προβλήματος

Το πρόβλημα "Ελάχιστη διαδρομή αθροίσματος σε ένα τρίγωνο" δηλώνει ότι σας δίνεται μια ακολουθία με τη μορφή ενός τριγώνου ακέραιων αριθμών. Τώρα ξεκινώντας από την επάνω σειρά ποιο είναι το ελάχιστο ποσό που μπορείτε να επιτύχετε όταν φτάσετε στην κάτω σειρά;

Παράδειγμα

Ελάχιστη διαδρομή αθροίσματος σε ένα τρίγωνο

  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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

Ο (Ν ^ 2), καθώς προχωρήσαμε σε κάθε σειρά και κάθε στήλη. Στη διαδικασία, ταξιδέψαμε σε κάθε κελί. Και αφού υπήρχαν κελιά O (N ^ 2) στο τρίγωνο και η μετάβαση για DP πήρε μόνο τη λειτουργία O (1). Έτσι, η πολυπλοκότητα του χρόνου είναι επίσης πολυώνυμη.

Διαστημική πολυπλοκότητα

Ο (Ν ^ 2) από τότε που δημιουργήσαμε έναν πίνακα 2D DP. Έτσι, η διαστημική πολυπλοκότητα είναι επίσης πολυώνυμη.