A, b සහ c දිගවල උපරිම කොටස් ගණන


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් කළු ගල් ByteDance Citrix ගූගල් 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 කින් බෙදන්නෙමු.

ප්රවේශය

ගැටළුව අපට ධනාත්මක පූර්ණ සංඛ්‍යාවක් N ලබා දෙන අතර තවත් පූර්ණ සංඛ්‍යාවක් a, b, c. මෙහිදී අපට අවශ්‍ය වන්නේ සංඛ්‍යාව a, b, සහ c ලෙස බෙදීමටයි. කොටස් ගණන උපරිම වන පරිදි අපි N බෙදිය යුතුයි. එබැවින් ගැටළුව විසඳීම සඳහා පළමුව කෑදර ප්‍රවේශයක් උත්සාහ කරමු. ගැටළුව විසඳීම සඳහා කෑදර ප්‍රවේශයක් වන්නේ a, b, සහ c වලින් කුඩාම දේ තෝරා ගැනීමයි. දැන් අපි N අවම කොටස් සමඟ කොටස් වලට බෙදමු. නමුත් එයට ඇල්ලීමක් තිබේ, කුඩාම කොටස N බෙදන්නේ නැත්නම් කුමක් කළ යුතුද? එවිට අපට සෑදිය නොහැකි ඉතිරි කොටස ඉතිරි වේ. එබැවින්, සමහර අවස්ථාවලදී කෑදර ප්‍රවේශයකින් අපට පිළිතුර සොයාගත නොහැකි බව මෙයින් සනාථ වේ.

එබැවින්, කෑදර ප්රවේශයක් භාවිතා කරමින් මෙය කරනවා වෙනුවට. අපි ගැටළුව විසඳා ගනිමු පුනරාවර්තනය. අපි N සඳහා පිළිතුර ලබා දෙන ශ්‍රිතයක් සාදන්නෙමු, එවිට මෙම ශ්‍රිතය Na, Nb සහ Nc යන අගයන් සමඟ හැඳින්වේ. මේ අනුව මුල් ගැටළුව කුඩා උපප්‍රශ්න වලට බෙදා ඇත. මෙම පුනරාවර්තන ශ්‍රිතයේ on ාතීය කාල සංකීර්ණතාව අපට අඩු කළ හැකිය ගතික වැඩසටහන්කරණය. ඩීපී සමඟ වැඩසටහන රේඛීය වේලාවෙන් ක්‍රියාත්මක වේ. මක්නිසාද යත් අපි කුඩා උපප්‍රශ්න සඳහා පිළිතුර ගබඩා කරන ඩීපී අරාවක් නිර්මාණය කරමු. ඒවායේ ප්‍රති result ලය අවශ්‍ය වූ විට අපි ඒවා පුනරාවර්තන විසඳුමක දී මෙන් නැවත ගණනය කිරීම වෙනුවට භාවිතා කරමු.

කේතය

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 දිගෙහි උපරිම කොටස් ගණන සොයා ගැනීමට ජාවා කේතය

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මොකද අපි දී ඇති පූර්ණ සංඛ්‍යාව තෙක් ලූපයක් ධාවනය කළා. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

මත), නැවත ගණනය කිරීම වළක්වා ගැනීම සඳහා අතරමැදි ප්‍රති results ල ගබඩා කිරීම සඳහා අපට 1D DP අරා නිර්මාණය කිරීමට සිදු වූ බැවිනි. මේ අනුව අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.