የከፍታዎች ብዛት ብዛት ሀ ፣ ለ እና ሐ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብላክ ሮክ ByteDance Citrix google ተራዳታ በ Uber
ተለዋዋጭ ፕሮግራም

ችግሩ “የርዝመቶች ብዛት ፣ ሀ እና ሐ” ከፍተኛ ቁጥር “አዎንታዊ” ቁጥር “N” እንደተሰጠዎት ይገልጻል ፣ እና N ን በመጠቀም ሊፈጠር የሚችል ከፍተኛውን የርዝመቶች ብዛት ሀ ፣ ለ እና ሐ ማግኘት ያስፈልግዎታል።

ለምሳሌ  

የከፍታዎች ብዛት ብዛት ሀ ፣ ለ እና ሐ

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

ማስረጃ

እዚህ ሁሉንም ክፍሎች በትንሽ ክፍል (= 2) ለመቁረጥ በመሞከር ከስግብግብ አቀራረብ ጋር ከሄድን። የመጨረሻውን የመጠን ክፍል መፍጠር አንችልም 1. ስለዚህ ርዝመቱን 4 በሁለት 2 ርዝመት ክፍሎች እና አንድ ባለ 4 ርዝመት ክፍል እንከፍላለን ፡፡

ቀረበ  

ችግሩ አዎንታዊ ኢንቲጀር N እና ሌሎች አንዳንድ ቁጥሮች ይሰጠናል ሀ ፣ ለ ፣ ሐ። እዚህ ቁጥሩን በ ሀ ፣ ለ እና በ. የክፍሎቹ ቁጥር ከፍተኛ እስከሆነ ድረስ N ን መከፋፈል ያስፈልገናል ፡፡ ስለዚህ ችግሩን ለመፍታት በመጀመሪያ ስግብግብ አካሄድን እንሞክር ፡፡ ችግሩን ለመፍታት በስግብግብነት የመያዝ አካሄድ አነስተኛውን ፣ ሀ እና ሐ መምረጥ ነው ፡፡ አሁን ኤን በትንሹ ርዝመት ወደ ክፍሎች እንከፍለዋለን ፡፡ ግን ለእሱ አንድ መያዝ አለ ፣ ትንሹ ክፍል ኤን ካልከፋፈለውስ? ከዚያ እኛ ማድረግ የማይቻልበትን ቀሪ ክፍል እንቀራለን። ስለዚህ ይህ በአንዳንድ ሁኔታዎች ስግብግብ አካሄድን በመጠቀም መልሱን ማግኘት እንደማንችል ያረጋግጥልናል ፡፡

ስለዚህ ፣ በስግብግብ አቀራረብ በመጠቀም ይህንን ከማድረግ ይልቅ ፡፡ ችግሩን በመጠቀም እንፈታዋለን ተደጋጋሚነት. ለ N መልስ የሚሰጠንን ተግባር እንሰራለን ፣ ከዚያ ይህ ተግባር እሴቶችን በና ፣ ኤንቢ እና ኤን. ስለሆነም የመጀመሪያው ችግር ወደ ትናንሽ ንዑስ ችግሮች ተከፍሏል ፡፡ እኛም በመጠቀም የዚህን ተደጋጋሚ ተግባር ጊዜያዊ ውስብስብነት መቀነስ እንችላለን ተለዋዋጭ ፕሮግራም. ከዲፒ ጋር ያለው መርሃግብር በተስተካከለ ጊዜ ይሠራል ፡፡ ምክንያቱም ለአነስተኛ ንዑስ ችግሮች መልሱን የሚያከማች የዲፒ ድርድር እንፈጥራለን ፡፡ ውጤታቸው በሚፈለግበት ጊዜ ሁሉ በድጋሜ መፍትሄ እንዳደረግነው እንደገና ከመቁጠር ይልቅ በቀላሉ እንጠቀማቸዋለን ፡፡

ተመልከት
የአብላጫ አካል ሌትኮድ መፍትሔ

ኮድ  

ርዝመቶች ሀ ፣ ለ እና ሐ ከፍተኛውን የክፍሎች ብዛት ለማግኘት የ 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

የከፍታውን የርዝመቶች ብዛት ፣ ጃ እና ሐ ለማግኘት የጃቫ ኮድ

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም የተሰጠው ኢንቲጀር እስከሚሆን ድረስ ቀለል ያለ ዑደት አከናውን ነበር ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እንደገና ላለመቆጠር መካከለኛ ውጤቶችን ለማከማቸት የ 1 ዲ ዲፒ ድርድር መፍጠር ነበረብን ፡፡ ስለዚህ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።