ထုတ်ကုန် K သည်ထက်လျော့နည်းရှိခြင်းအားလုံးနောက်ဆက်တွဲရေတွက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် ByteDance Capital One CodeNation Databricks Expedia Yandex
အခင်းအကျင်း Dynamic Programming

ပြproductနာ“ ထုတ်ကုန် K သည်ထက်နည်းသောနောက်ဆက်တွဲများအားလုံးကိုရေတွက်ပါ” ကသင့်အားကိန်းဂဏန်းများကိုပေးထားသည်ဟုဖော်ပြသည်။ ယခုပေးထားသောသွင်းအားစု K. ထက်လျော့နည်းကုန်ပစ္စည်းရှိသည်သောနောက်ဆက်တွဲ၏နံပါတ်ရှာပါ။

နမူနာ

ထုတ်ကုန် K သည်ထက်လျော့နည်းရှိခြင်းအားလုံးနောက်ဆက်တွဲရေတွက်

a[] = {1, 2, 3, 4, 5}
k = 8
Number of subsequences less than 8: 11

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

ပေးထားသော than (= 11) ထက်လျော့နည်းထုတ်ကုန်ရှိသည်သောနောက်ဆက်တွဲ 8 ရှိပါတယ်။ အဆိုပါနောက်ဆက်တွဲအထက်ပါပုံတွင်ပြနေကြသည်။

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

ဒီပြproblemနာကကျွန်တော်တို့ကိုကိန်းတန်းတွေ၊ K. ကိန်းတစ်ခုပေးထားတယ်။ နောက်ဆက်တွဲအရေအတွက်ကို K. ထက်နည်းတဲ့ထုတ်ကုန်တွေရှာဖို့ပြောတယ်။ တစ် ဦး ကနုံချဉ်းကပ်သည်ဤပာ generate ပြီးတော့ထုတ်ပေး sequence ကိုကျွန်တော်တို့ရဲ့အခြေအနေများကျေနပ်သို့မဟုတ်မရှိမရှိစစ်ဆေးအမြဲတမ်းဖြစ်သနည်း

ဒီနုံဖြေရှင်းနည်းကငါတို့ရဲ့အချိန်ကန့်သတ်ချက်ထက်ကျော်လွန်လိမ့်မယ်။ ဒါကြောင့်ပြgivenနာကိုပေးထားတဲ့အချိန်ကန့်သတ်ချက်အောက်မှာဖြေရှင်းရန်။ ကျွန်ုပ်တို့အသုံးပြုရန်လိုအပ်သည် Dynamic Programming။ ဒီတော့ဒီမှာက input array ကိုဖြတ်သွားမယ်။ ဖြတ်သန်းသွားစဉ် DP ဇယားကိုတစ်ပြိုင်တည်းဖြည့်လိမ့်မည်။ ဒီ DP ပြforနာအတွက်ကျွန်တော်တို့မှာပြည်နယ်နှစ်ခုရှိတယ်၊ ပထမကအခုထိထုတ်ကုန်ဖြစ်တယ်၊ ဒုတိယက input array အတွက်အညွှန်းဖြစ်တယ်။ ကျွန်ုပ်တို့သည်ထုတ်ကုန်ဖြင့်စတင်ပြီးလိုအပ်သောရလဒ်ရရှိနိုင်ခြင်းရှိမရှိစစ်ဆေးသည် input array မှနံပါတ်များ / ဒြပ်စင်များနှင့်ဖြစ်သည်။

ကျွန်ုပ်တို့၏ dp ခင်းကျင်းသောဆဲလ် dp [i] [j] သည် i ထက်ထုတ်ကုန်လျော့နည်းပြီး input ၏ပထမဆုံး j element များကို အသုံးပြု၍ ဖွဲ့စည်းထားသည့်နောက်ဆက်တွဲအရေအတွက်ကိုဆိုလိုသည်။ ဒါကြောင့် dp [i] [j] ကိုရှာဖို့အတွက် dp [i / a [j]] [j] နဲ့ dp [i] [j-1] အပေါ်မှီခိုနေရသည်။ ဒီ [i]> i, ဒီ element ကိုနောက်ဆက်တွဲသို့ယူလျှင် [i] သူ့ဟာသူ K. ထက်သာ။ ကြီးမြတ်လိမ့်မယ်ဆိုလိုတာကဒီ element ကိုထည့်သွင်းစဉ်းစားမည်မဟုတ်ပါ။ ဒါကြောင့်ကျွန်တော်တို့ဟာထုတ်ကုန်တွေ K. ထက်နည်းတဲ့နောက်ဆက်တွဲတွေအားလုံးကိုရေတွက်ကြည့်မယ်။

ကုဒ်

ထုတ်ကုန်သည် K ထက်နည်းသောနောက်ဆက်တွဲများအားလုံးကိုရေတွက်ရန် C ++ ကုဒ်ဖြစ်သည်

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[] = {1, 2, 3, 4, 5};
    int n = (sizeof a)/(sizeof a[0]);
    int k = 8;
    int dp[k][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1;i<k;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = dp[i][j-1];
            if (a[j-1] <= i && a[j-1] > 0)
                dp[i][j] += dp[i/a[j-1]][j-1] + 1;
        }
    }

    cout<<dp[k-1][n];
}
11

ထုတ်ကုန်သည် K ထက်နည်းသောနောက်ဆက်တွဲများအားလုံးကိုရေတွက်ရန် Java ကုဒ်ဖြစ်သည်

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int a[] = {1, 2, 3, 4, 5};
      int n = a.length;
      int k = 8;
      int dp[][] = new int[k][n+1];
      for(int i=0;i<k;i++)
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = 0;

      for (int i=1;i<k;i++){
          for (int j=1;j<=n;j++){
              dp[i][j] = dp[i][j-1];
              if (a[j-1] <= i && a[j-1] > 0)
                  dp[i][j] += dp[i/a[j-1]][j-1] + 1;
          }
      }
    System.out.println(dp[k-1][n]);
  }
}
11

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

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

အို (N * K), အကြောင်းကတော့ပြည်နယ်နှစ်ခုကတစ်ခုက input array အတွက်အညွှန်းကိန်းတစ်ခုဖြစ်ပြီးနောက်တစ်ခုကတော့နိမ့်ကျတဲ့ကန့်သတ်ချက်ရဲ့ထုတ်ကုန်ဖြစ်လို့ပဲ။ ၎င်းတို့တွင် N နှင့် K အထက်ဘောင်းရှိကြသည်၊ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည် polynomial ဖြစ်သည်။

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

အို (N * K), ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ N * K cell တွေပါတဲ့ 2D DP table တစ်ခုကိုဖန်တီးခဲ့တယ်။ အရှင်အာကာသရှုပ်ထွေးကိုလည်း polynomial ဖြစ်ပါတယ်။