Максимален брой сегменти с дължини a, b и c


Ниво на трудност M
Често задавани в Амазонка BlackRock ByteDance Citrix Google Терадата Uber
Динамично програмиране

Проблемът „Максимален брой сегменти с дължини a, b и c“ гласи, че ви е дадено положително цяло число N и трябва да намерите максималния брой сегменти с дължини a, b и c, които могат да се образуват с помощта на N.

Пример

Максимален брой сегменти с дължини a, b и c

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

Обяснение

Тук, ако тръгнем с алчния подход, опитвайки се да изрежем всички сегменти с най-малкия сегмент (= 2). Няма да можем да създадем последния сегмент с размер 1. По този начин разделяме дължината 4 с два сегмента с дължина 2 и един сегмент с дължина 4.

Подход

Проблемът ни предоставя положително цяло число N и някои други цели числа a, b, c. Тук искаме да разделим броя на дължини на a, b и c. Трябва да разделим N така, че броят на сегментите да е максимален. Така че, за да разрешим проблема, нека първо опитаме алчен подход. Алчен подход за решаване на проблема е изборът на най-малкия от a, b и c. Сега разделяме N на сегменти с минимална дължина. Но има уловка в това, какво ще стане, ако най-малкият сегмент не разделя N? Тогава ще ни остане остатъчен сегмент, който не е възможно да се направи. Така че, това потвърждава, че в някои случаи не можем да намерим отговора, използвайки алчен подход.

Така че, вместо да правите това, използвайки алчен подход. Решаваме проблема с помощта рекурсия. Правим функция, която ни дава отговор за N, след което тази функция се извиква със стойности Na, Nb и Nc. По този начин първоначалният проблем е разделен на по-малки подпроблеми. Също така можем да намалим експоненциалната времева сложност на тази рекурсивна функция, използвайки динамично програмиране. Програмата с DP ще работи в линейно време. Защото ще създадем DP масив, който ще съхранява отговора за по-малки подпроблеми. И винаги, когато се изисква техният резултат, ние просто ги използваме, вместо да ги преизчисляваме, както направихме в рекурсивно решение.

код

C ++ код за намиране на максималния брой сегменти с дължини a, b и 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

Java код за намиране на максималния брой сегменти с дължини a, b и c

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

Анализ на сложността

Сложност във времето

НА), защото просто изпълнихме цикъл до даденото цяло число. По този начин сложността на времето е линейна.

Сложност на пространството

НА), защото трябваше да създадем 1D DP масив за съхраняване на междинните резултати, за да избегнем преизчисляване. По този начин сложността на пространството също е линейна.