Баруун тооны гурвалжин дахь замын хамгийн их нийлбэр


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Citrix DE Шоу 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 хүснэгтэд ижил оролтын массивыг ашигладаг. Тиймээс бид шинэ АН массив үүсгэх орон зайг аваагүй тул орон зайн нарийн төвөгтэй байдал тогтмол байдаг.