A, b, c урттай сегментүүдийн хамгийн их тоо


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны БлэкРок БайтДанс Citrix Google-ийн Teradata Uber
Динамик програмчлал

“A, b, c урттай сегментүүдийн хамгийн их тоо” гэсэн бодлогод танд эерэг N бүхэл тоо өгөгдөж байгаа бөгөөд N ашиглан үүсгэж болох a, b, c уртын сегментүүдийн тоог олох хэрэгтэй.

Жишээ нь

A, b, c урттай сегментүүдийн хамгийн их тоо

N = 7
a = 5, b = 2, c = 3
3

Тайлбар

Хэрэв бид бүх сегментүүдийг хамгийн жижиг сегментээр (= 2) таслахыг хичээвэл шунахай хандлагаар явах болно. Бид 1-р хэмжээтэй сүүлийн сегментийг үүсгэх боломжгүй болно. Тиймээс бид 4-ийн уртыг 2 урттай 4 сегмент, XNUMX урттай сегментээр хуваана.

арга барил

Асуудал нь бидэнд эерэг бүхэл тоо N, бусад бүх a, b, c бүхэл тоонуудыг өгдөг. Энд бид тоог a, b, c-ийн уртаар хуваахыг хүсч байна. Бид сегментийн тоо хамгийн их байхаар N-ийг хуваах хэрэгтэй. Тиймээс асуудлыг шийдэхийн тулд эхлээд шунахай арга замыг туршиж үзье. Асуудлыг шийдэхийн тулд шунахай хандлага бол а, б, в-ийн хамгийн бага хэсгийг сонгох явдал юм. Одоо бид N-ийг хамгийн бага урттай сегмент болгон хувааж байна. Гэхдээ энэ нь сонирхолтой зүйл юм, хэрвээ хамгийн жижиг хэсэг нь N-ийг хуваахгүй бол яах вэ? Дараа нь хийх боломжгүй үлдсэн сегменттэй үлдэх болно. Тиймээс энэ нь бид зарим тохиолдолд шунахай аргыг ашиглан хариултаа олж чадахгүй байгааг баталж байна.

Тиймээс, шунахай аргыг ашиглан үүнийг хийхийн оронд. Бид асуудлыг ашиглан шийддэг давтлага. Бид N-ийн хариуг өгдөг функцийг хийдэг бөгөөд энэ функц нь өөрийгөө Na, Nb, Nc гэсэн утгуудаар дууддаг. Тиймээс анхны асуудлыг жижиг дэд асуудлуудад хуваажээ. Бид энэ рекурсив функцийн экспоненциал цагийн нарийн төвөгтэй байдлыг багасгаж болно динамик програмчлал. АН-тай програм нь шугаман хугацаанд ажиллана. Учир нь бид жижиг дэд асуудлуудын хариуг хадгалах DP массивыг үүсгэх болно. Үр дүн нь шаардагдах бүрт бид тэдгээрийг рекурсив шийдэлд оруулсан шиг дахин тооцоолохын оронд ашигладаг.

код

A, b, c урттай сегментүүдийн хамгийн их тоог олох C ++ код

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

int main()
{
  int n = 7, a = 5, b = 2, c = 3;
  int dp[n + 1];
  memset(dp, -1, sizeof(dp));
  // base case
  dp[0] = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] != -1) {
            if(i + a <= n )dp[i + a] = max(dp[i] + 1, dp[i + a]);
            if(i + b <= n )dp[i + b] = max(dp[i] + 1, dp[i + b]);
            if(i + c <= n )dp[i + c] = max(dp[i] + 1, dp[i + c]);
    }
  }
    cout<<dp[n];
}
3

A, b, c урттай сегментүүдийн хамгийн их тоог олох Java код

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int n = 7, a = 5, b = 2, c = 3;
    int dp[] = new int[n+1];
    for(int i=0;i<=n;i++)dp[i] = -1;
    // base case
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
      if (dp[i] != -1) {
              if(i + a <= n )dp[i + a] = Math.max(dp[i] + 1, dp[i + a]);
              if(i + b <= n )dp[i + b] = Math.max(dp[i] + 1, dp[i + b]);
              if(i + c <= n )dp[i + c] = Math.max(dp[i] + 1, dp[i + c]);
      }
    }
    System.out.println(dp[n]);
  }
}
3

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид өгөгдсөн бүхэл тоо хүртэл давталт хийсэн. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид дахин тооцоолохоос зайлсхийхийн тулд завсрын үр дүнг хадгалах 1D DP массивыг бий болгох ёстой байсан. Тиймээс орон зайн нарийн төвөгтэй байдал нь мөн шугаман юм.