എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ കറുത്ത പാറ ബൈറ്റ്ഡാൻസ് ക്സെൻ ഗൂഗിൾ തെരദത യൂബർ
ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

“എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം സെഗ്‌മെന്റുകൾ” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ഒരു പോസിറ്റീവ് സംഖ്യ N നൽകിയിട്ടുണ്ടെന്നും N ഉപയോഗിച്ച് രൂപം കൊള്ളാവുന്ന എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം

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

വിശദീകരണം

അത്യാഗ്രഹപരമായ സമീപനത്തോടെയാണ് ഞങ്ങൾ ഇവിടെ പോകുന്നതെങ്കിൽ, എല്ലാ സെഗ്‌മെന്റുകളും ചെറിയ സെഗ്‌മെന്റ് (= 2) ഉപയോഗിച്ച് മുറിക്കാൻ ശ്രമിക്കുന്നു. വലുപ്പം 1 ന്റെ അവസാന സെഗ്മെന്റ് സൃഷ്ടിക്കാൻ ഞങ്ങൾക്ക് കഴിയില്ല. അങ്ങനെ ഞങ്ങൾ നീളം 4 നെ രണ്ട് 2 നീളമുള്ള സെഗ്‌മെന്റുകളും ഒരു 4 നീളമുള്ള സെഗ്‌മെന്റും ഉപയോഗിച്ച് വിഭജിക്കുന്നു.

സമീപനം

പ്രശ്നം ഞങ്ങൾക്ക് ഒരു പോസിറ്റീവ് സംഖ്യ N നൽകുന്നു, കൂടാതെ മറ്റ് ചില സംഖ്യകൾ a, b, c. ഇവിടെ, എ, ബി, സി എന്നിവയുടെ നീളത്തിൽ സംഖ്യ വിഭജിക്കാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. സെഗ്‌മെന്റുകളുടെ എണ്ണം പരമാവധി വർദ്ധിക്കുന്ന തരത്തിൽ നമ്മൾ N വിഭജിക്കണം. അതിനാൽ പ്രശ്നം പരിഹരിക്കുന്നതിന്, ആദ്യം അത്യാഗ്രഹപരമായ ഒരു സമീപനം പരീക്ഷിക്കാം. A, b, c എന്നിവയിൽ ഏറ്റവും ചെറിയവ തിരഞ്ഞെടുക്കുന്നതാണ് പ്രശ്നം പരിഹരിക്കാനുള്ള അത്യാഗ്രഹപരമായ സമീപനം. ഇപ്പോൾ നമ്മൾ N നെ ഏറ്റവും കുറഞ്ഞ നീളമുള്ള ഭാഗങ്ങളായി വിഭജിക്കുന്നു. എന്നാൽ ഇതിന് ഒരു ക്യാച്ച് ഉണ്ട്, ഏറ്റവും ചെറിയ സെഗ്മെന്റ് N നെ വിഭജിക്കുന്നില്ലെങ്കിലോ? അപ്പോൾ നമുക്ക് നിർമ്മിക്കാൻ കഴിയാത്ത ഒരു സെഗ്മെന്റ് ശേഷിക്കും. അതിനാൽ, ചില സന്ദർഭങ്ങളിൽ അത്യാഗ്രഹപരമായ സമീപനം ഉപയോഗിച്ച് ഞങ്ങൾക്ക് ഉത്തരം കണ്ടെത്താൻ കഴിയില്ലെന്ന് ഇത് സ്ഥിരീകരിക്കുന്നു.

അതിനാൽ, അത്യാഗ്രഹപരമായ സമീപനം ഉപയോഗിച്ച് ഇത് ചെയ്യുന്നതിനുപകരം. ഉപയോഗിക്കുന്നതിലൂടെ ഞങ്ങൾ പ്രശ്നം പരിഹരിക്കുന്നു ആവർത്തനം. N- നുള്ള ഉത്തരം നൽകുന്ന ഒരു ഫംഗ്ഷൻ ഞങ്ങൾ നിർമ്മിക്കുന്നു, തുടർന്ന് ഈ ഫംഗ്ഷൻ സ്വയം Na, Nb, Nc എന്നീ മൂല്യങ്ങൾ ഉപയോഗിച്ച് വിളിക്കുന്നു. അങ്ങനെ യഥാർത്ഥ പ്രശ്നം ചെറിയ ഉപപ്രശ്നങ്ങളായി തിരിച്ചിരിക്കുന്നു. ഈ ആവർത്തന ഫംഗ്ഷന്റെ എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണത കുറയ്‌ക്കാനും ഞങ്ങൾക്ക് കഴിയും ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. ഡിപിയുമായുള്ള പ്രോഗ്രാം ലീനിയർ സമയത്ത് പ്രവർത്തിക്കും. കാരണം ഞങ്ങൾ ഒരു ഡിപി അറേ സൃഷ്ടിക്കും, അത് ചെറിയ ഉപപ്രശ്നങ്ങൾക്കുള്ള ഉത്തരം സംഭരിക്കും. അവയുടെ ഫലം ആവശ്യമുള്ളപ്പോഴെല്ലാം ഞങ്ങൾ ആവർത്തിച്ചുള്ള പരിഹാരത്തിൽ ചെയ്തതുപോലെ അവ വീണ്ടും കംപ്യൂട്ട് ചെയ്യുന്നതിന് പകരം അവ ഉപയോഗിക്കുന്നു.

കോഡ്

എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#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

എ, ബി, സി നീളങ്ങളുടെ പരമാവധി എണ്ണം കണ്ടെത്തുന്നതിനുള്ള ജാവ കോഡ്

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), കാരണം വീണ്ടും കണക്കുകൂട്ടൽ ഒഴിവാക്കാൻ ഇന്റർമീഡിയറ്റ് ഫലങ്ങൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾ 1 ഡി ഡിപി അറേ സൃഷ്ടിക്കേണ്ടതുണ്ട്. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.