কে এর চেয়ে কম পণ্যসম্পন্ন সমস্ত অনুচ্ছেদ গণনা করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ByteDance ক্যাপিটাল ওয়ান কোডনেশন ডেটাব্রিক্স এক্সপিডিয়া ইয়ানডেক্স
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যাটি "কে এর চেয়ে কম পণ্যযুক্ত সমস্ত উপসংখ্যা গণনা করুন" বলে দেয় যে আপনাকে পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়। এখন এমন কোনও উপসর্গের সংখ্যার সন্ধান করুন যা প্রদত্ত ইনপুট কে-এর চেয়ে কম পণ্য রয়েছে

উদাহরণ

কে এর চেয়ে কম পণ্যসম্পন্ন সমস্ত অনুচ্ছেদ গণনা করুন

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

ব্যাখ্যা

এখানে 11 টি উপসর্গ রয়েছে যা প্রদত্ত কে (= 8) এর চেয়ে কম পণ্য রয়েছে। উপসর্গগুলি উপরের চিত্রটিতে প্রদর্শিত হবে।

অভিগমন

সমস্যাটি আমাদের পূর্ণসংখ্যার ক্রম এবং একটি পূর্ণসংখ্যক কে দিয়েছিল then তারপরে আমাদের কে অনুমানের, কম উপগ্রহ, বা সাববারিগুলির সাথে লেনদেনের ক্ষেত্রে কম সংখ্যক উপসর্গের সংখ্যা খুঁজে পেতে বলা হয় So একটি নিষ্পাপ দৃষ্টিভঙ্গি সর্বদা এই অনুক্রমগুলি উত্পন্ন করার জন্য এবং তারপরে তৈরি হওয়া ক্রমটি আমাদের শর্তগুলি পূরণ করে কিনা তা পরীক্ষা করে দেখুন?

এই নিষ্পাপ সমাধান অবশ্যই আমাদের সময়সীমা অতিক্রম করবে। সুতরাং নির্দিষ্ট সময়সীমাবদ্ধতায় সমস্যা সমাধানের জন্য solve আমাদের ব্যবহার করা দরকার ডায়নামিক প্রোগ্রামিং। সুতরাং এখানে আমরা ইনপুট অ্যারে পেরিয়ে যাব। ট্র্যাভারসাল চলাকালীন, আমরা একই সাথে ডিপি টেবিলটি পূরণ করব। এই ডিপি সমস্যার জন্য আমাদের দুটি রাজ্য রয়েছে, প্রথমটি এখন অবধি পণ্য এবং দ্বিতীয়টি ইনপুট অ্যারের সূচক। আমরা পণ্যটি দিয়ে শুরু করি এবং আমরা ইনপুট অ্যারে থেকে সংখ্যা / উপাদানগুলির সাথে প্রয়োজনীয় ফলাফল পেতে পারি কিনা তা যাচাই করি।

আমাদের ডিপি অ্যারে সেল ডিপি [i] [জে] আমার কাছে কম পণ্য রয়েছে এবং ইনপুটটির প্রথম জে উপাদান ব্যবহার করে গঠিত এমন উপস্তরের সংখ্যা বোঝায়। সুতরাং ডিপি [i] [জে] সন্ধানের জন্য, আমরা ডিপি [আই / এ [জে]] [জে] এবং ডিপি [আই] [জে -১] এর উপর নির্ভরশীল। সুতরাং যদি একটি [i]> i, এই উপাদানটিকে পরবর্তী অংশে নিয়ে যাওয়ার অর্থ হ'ল একটি [i] নিজেই কে এর চেয়ে বড় Thus সুতরাং এই উপাদানটি বিবেচনা করা হবে না। সুতরাং আমরা কে এর চেয়ে কম পণ্য থাকা সমস্ত অনুচ্ছেদগুলি গণনা করি

কোড

কে ++ এর চেয়ে কম পণ্যযুক্ত সমস্ত অনুচ্ছেদ গণনা করতে কোড +

#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

কে এর চেয়ে কম পণ্যসম্পন্ন সকল অনুচ্ছেদ গণনা করার জন্য জাভা কোড

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * কে), কারণ দুটি রাজ্য রয়েছে একটি হ'ল ইনপুট অ্যারের সূচক এবং অপরটি উপসীমা সীমাটির পণ্য of তাদের একটি উপরের সীমানা এন এবং কে রয়েছে, সুতরাং সময় জটিলতা বহুপদী হয়।

স্পেস জটিলতা ity

ও (এন * কে), কারণ আমরা এন * কে সেল দিয়ে একটি 2 ডি ডিপি টেবিল তৈরি করেছি। সুতরাং স্থান জটিলতাও বহুপদী।