အရှည် a, b နှင့် c ၏အစိတ်အပိုင်းများအများဆုံးအရေအတွက်  


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ BlackRock ByteDance Citrix Google Teradata Uber
Dynamic Programming

ပြproblemနာက“ a, b, c အရှည်ဆုံး၏အပိုင်းအရေအတွက်” သည်အပြုသဘောဆောင်သောကိန်းဂဏန်း N ကိုပေးထားပြီးသင် N. သုံး၍ ဖွဲ့စည်းနိုင်သည့်အရှည် a, b နှင့် c ၏အမြင့်ဆုံးအရေအတွက်ကိုရှာဖွေရန်လိုအပ်သည်

နမူနာ  

အရှည် a, b နှင့် c ၏အစိတ်အပိုင်းများအများဆုံးအရေအတွက်တွယ်အပ်

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

ရှင်းလင်းချက်

ဤတွင်ကျွန်ုပ်တို့သည်လောဘကြီးသောချဉ်းကပ်နည်းဖြင့်သွားပါက segments များအားလုံးကိုအငယ်ဆုံးအပိုင်း (2) ဖြင့်ဖြတ်ရန်ကြိုးစားသည်။ ကျွန်ုပ်တို့သည်နောက်ဆုံးအရွယ်အစား၏နောက်ဆုံးအပိုင်းကိုမဖန်တီးနိုင်ပါ။ ထို့ကြောင့်အရှည် ၂ ခုကို ၂ အရှည်အပိုင်း ၂ ခုနှင့် ၄ ခုအရှည်အပိုင်း ဟူ၍ ခွဲပါ။

ချဉ်းကပ်နည်း  

ပြproblemနာကအပြုသဘောဆောင်တဲ့ကိန်းဂဏန်း N ကိုပေးတယ်၊ တစ်ချို့ကိန်း a, b, c ။ ဒီကိန်းဂဏန်းကို a, b, c ရဲ့အရှည်နဲ့စားချင်တယ်။ ကျွန်ုပ်တို့သည် segments များ၏အရေအတွက်သည်အများဆုံးဖြစ်ကြောင်း N ကိုဝေရန်လိုသည်။ ဒီတော့ပြproblemနာကိုဖြေရှင်းဖို့လောဘကြီးတဲ့ချဉ်းကပ်နည်းကိုအရင်စမ်းကြည့်ရအောင်။ ပြproblemနာကိုဖြေရှင်းရန်လောဘကြီးသောချဉ်းကပ်နည်းသည် a, b နှင့် c တို့၏အငယ်ဆုံးသောရွေးချယ်မှုကိုဖြစ်သည်။ ယခုကျွန်ုပ်တို့သည် N ကိုအနိမ့်ဆုံးအရှည်ဖြင့် segments များအဖြစ်ခွဲလိုက်သည်။ ဒါပေမယ့်အဲဒါကိုဖမ်းယူနိုင်ဖို့အသေးငယ်ဆုံးအပိုင်းက N ကိုမခွဲဘူးဆိုရင်ကော။ ထိုအခါကျွန်ုပ်တို့သည်လုပ်ရန်မဖြစ်နိုင်သည့်ကျန်ရှိသောအစိတ်အပိုင်းနှင့်ကျန်လိမ့်မည်။ ထို့ကြောင့်၊ အချို့သောကိစ္စရပ်များတွင်လောဘကြီးသောချဉ်းကပ်နည်းကို သုံး၍ အဖြေကိုကျွန်ုပ်တို့ရှာမတွေ့နိုင်ပါ။

လည်းကြည့်ရှုပါ
အများစု Element ကို Leetcode ဖြေရှင်းချက်

ဒါကြောင့်လောဘကြီးတဲ့နည်းလမ်းကိုသုံးပြီးလုပ်မယ့်အစား။ ကျနော်တို့ပြusingနာကိုအသုံးပြုပြီးဖြေရှင်း ပြန်လည်။ ကျွန်တော်တို့ကို N အတွက်အဖြေပေးတဲ့ function တစ်ခုကိုလုပ်ပါတယ်။ အဲ့ဒီ function ကသူ့ဟာသူ Na, Nb, Nc လို့ခေါ်ပါတယ်။ ထို့ကြောင့်မူလပြproblemနာကိုသေးငယ်သော subproblems အဖြစ်ခွဲထားသည်။ ဤသည်ကို အသုံးပြု၍ ဤထပ်ခါတလဲလဲလုပ်ဆောင်မှု၏အဆရှုပ်ထွေးမှုကိုလည်းလျှော့ချနိုင်သည် dynamic programming ကို။ DP နှင့်အတူအစီအစဉ်ကို linear အချိန်တွင် run ပါလိမ့်မယ်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်သေးငယ်သော subproblems များအတွက်အဖြေကိုသိမ်းဆည်းမည့် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း  

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာလို့လဲဆိုတော့ငါတို့ကပေးထားတဲ့ကိန်းပြည့်အထိကွင်းဆက်ကိုသာလုပ်ခဲ့တယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

လည်းကြည့်ရှုပါ
မီတာအားဖြင့်ကှဲလှဲပေါင်းလဒ်နှင့်အတူ Subset

အာကာသရှုပ်ထွေးမှု

အို (N)၊ ပြန်လည်တွက်ချက်ခြင်းကိုရှောင်ရှားရန်အတွက်အလယ်အလတ်ရလဒ်များကိုသိုလှောင်ရန်အတွက် 1D DP ခင်းကျင်းမှုတစ်ခုကိုဖန်တီးခဲ့ရသည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။