K ට වඩා අඩු නිෂ්පාදනයක් ඇති සියලුම පසු විපරම් ගණන් කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ByteDance ප්රාග්ධන එක් කෝඩ්නේෂන් දත්ත සමුදායන් Expedia Yandex
අරා ගතික වැඩසටහන්කරණය

“K ට වඩා අඩු නිෂ්පාදනයක් ඇති සියලුම පසු විපරම් ගණන් කරන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට පූර්ණ සංඛ්‍යා පෙළක් ලබා දී ඇති බවයි. දී ඇති ආදානයකට වඩා අඩු නිෂ්පාදනයක් ඇති පසු විපරම් ගණන දැන් සොයා ගන්න.

උදාහරණයක්

K ට වඩා අඩු නිෂ්පාදනයක් ඇති සියලුම පසු විපරම් ගණන් කරන්න

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

පැහැදිලි කිරීම

ලබා දී ඇති k (= 11) ට වඩා අඩු නිෂ්පාදනයක් ඇති පසු විපරම් 8 ක් ඇත. පසු විපරම් ඉහත රූපයේ දැක්වේ.

ප්රවේශය

ගැටළුව අපට පූර්ණ සංඛ්‍යා අනුපිළිවෙලක් ලබා දී ඇති අතර කේ. නිඛිල සංඛ්‍යාවක් පසුව කේ ට වඩා අඩු නිෂ්පාදනයක් ඇති පසු විපරම් ගණන සොයා ගන්නා ලෙස අපට කියනු ලැබේ. බොළඳ ප්‍රවේශයක් යනු සැමවිටම මෙම අනුක්‍රමයන් උත්පාදනය කර උත්පාදනය කළ අනුක්‍රමය අපගේ කොන්දේසි සපුරාලන්නේද යන්න පරීක්ෂා කිරීමයි.

මෙම බොළඳ විසඳුම නිසැකවම අපගේ කාල සීමාව ඉක්මවා යනු ඇත. එබැවින් නියමිත කාල සීමාව යටතේ ගැටළුව විසඳීම. අප භාවිතා කළ යුතුය ගතික වැඩසටහන්කරණය. ඉතින් මෙන්න අපි ආදාන අරාව හරහා ගමන් කරන්නෙමු. සංචලනය අතරතුර, අපි එකවර ඩීපී වගුව පුරවන්නෙමු. මෙම ඩීපී ගැටළුව සඳහා අපට ප්‍රාන්ත දෙකක් තිබේ, පළමුවැන්න මේ වන තෙක් නිෂ්පාදිතය වන අතර දෙවැන්න ආදාන අරාව සඳහා දර්ශකය වේ. අපි නිෂ්පාදිතයෙන් ආරම්භ කර ආදාන අරාවෙන් සංඛ්‍යා / මූලද්‍රව්‍ය සමඟ අවශ්‍ය ප්‍රති result ලය ලබා ගත හැකිදැයි පරීක්ෂා කරමු.

අපගේ dp අරා කොටුව dp [i] [j] මඟින් දැක්වෙන්නේ මට වඩා අඩු නිෂ්පාදනයක් ඇති සහ ආදානයේ පළමු j මූලද්‍රව්‍ය භාවිතා කර සෑදී ඇති පසු විපරම් ගණනයි. එබැවින් dp [i] [j] සොයා ගැනීම සඳහා, අපි dp [i / a [j]] [j] සහ dp [i] [j-1] මත රඳා පවතී. එබැවින් [i]> i නම්, මෙම මූලද්‍රව්‍යය පසු විපරමට ගෙන යාමෙන් අදහස් වන්නේ [i] ම K ට වඩා විශාල බවයි. එබැවින් මෙම මූලද්‍රව්‍යය නොසැලකේ. 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 ට වඩා අඩු නිෂ්පාදනයක් ඇති සියලුම පසු විපරම් ගණනය කිරීමට ජාවා කේතය

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 ඇත, එබැවින් කාල සංකීර්ණතාව බහුපද වේ.

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

ඕ (එන් * කේ), මොකද අපි N * K සෛල සහිත 2D DP වගුවක් නිර්මාණය කළා. මේ අනුව අවකාශයේ සංකීර්ණතාව ද බහුපද වේ.