រាប់ការបន្តទាំងអស់ដែលមានផលិតផលតិចជាង K  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ByteDance សាលាមួយ លេខកូដ មូលដ្ឋានទិន្នន័យ Expedia Yandex
អារេ ការសរសេរកម្មវិធីឌីណាមិក

បញ្ហា“ រាប់ផលបន្តបន្ទាប់ទាំងអស់ដែលមានផលិតផលតិចជាង K” ចែងថាអ្នកត្រូវបានផ្តល់នូវចំនួនគត់។ ឥឡូវរកឃើញចំនួនបន្តបន្ទាប់ដែលមានផលិតផលតិចជាងការបញ្ចូល K ដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍  

រាប់ការបន្តទាំងអស់ដែលមានផលិតផលតិចជាង K

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

ការពន្យល់

មានជាបន្តបន្ទាប់ចំនួន ១១ ដែលមានផលិតផលតិចជាង k (= ៨) ។ ជាបន្តបន្ទាប់ត្រូវបានបង្ហាញនៅក្នុងរូបភាពខាងលើ។

វិធីសាស្រ្ត  

បញ្ហាបានផ្តល់ឱ្យយើងនូវលំដាប់នៃចំនួនគត់ហើយនិងចំនួនគត់។ បន្ទាប់មកយើងត្រូវបានគេប្រាប់អោយរកចំនួនបន្តបន្ទាប់ដែលមានផលិតផលតិចជាងឃ។ ដូច្នេះរាល់ពេលដែលយើងទាក់ទងនឹងបណ្តុំអនុភាគរងរឺរងរង។ វិធីឆោតល្ងង់គឺតែងតែដើម្បីបង្កើតលំដាប់ទាំងនេះហើយបន្ទាប់មកពិនិត្យមើលថាតើលំដាប់ដែលបានបង្កើតពេញចិត្តនឹងលក្ខខណ្ឌរបស់យើងឬអត់?

ដំណោះស្រាយឆោតល្ងង់នេះច្បាស់ជាហួសពេលកំណត់របស់យើងហើយ។ ដូច្នេះដើម្បីដោះស្រាយបញ្ហាក្រោមពេលវេលាដែលបានកំណត់។ យើងតម្រូវឱ្យប្រើ ការសរសេរកម្មវិធីឌីណាមិក។ ដូច្នេះនៅទីនេះយើងនឹងឆ្លងកាត់អារេបញ្ចូល។ ក្នុងកំឡុងពេលឆ្លងកាត់យើងនឹងបំពេញតារាង DP ក្នុងពេលដំណាលគ្នា។ យើងមានរដ្ឋពីរសម្រាប់បញ្ហា DP នេះទីមួយគឺផលិតផលរហូតមកដល់ពេលនេះនិងទីពីរគឺសន្ទស្សន៍សម្រាប់អារេបញ្ចូល។ យើងចាប់ផ្តើមជាមួយផលិតផលហើយពិនិត្យមើលថាតើយើងអាចទទួលបានលទ្ធផលដែលត្រូវការជាមួយលេខ / ធាតុពីអារេបញ្ចូល។

សូម​មើល​ផង​ដែរ
ដំណោះស្រាយលេខ Leetcode ចំនួន ៦៩ អតិបរមា

dp cell cell dp [i] [j] បង្ហាញពីចំនួនបន្តបន្ទាប់ដែលមានផលិតផលតិចជាងខ្ញុំហើយត្រូវបានបង្កើតឡើងដោយប្រើធាតុ j ដំបូងនៃធាតុបញ្ចូល។ ដូច្នេះដើម្បីស្វែងរក dp [i] [j] យើងពឹងលើ dp [i / a [j]] [ច] និង dp [i] [j-1] ។ ដូច្នេះប្រសិនបើ a [i]> ខ្ញុំយកធាតុនេះទៅជាបន្តវាមានន័យថា a [i] ខ្លួនវាធំជាង K. ដូច្នេះធាតុនេះនឹងមិនត្រូវបានគេពិចារណាទេ។ ដូច្នេះនោះគឺជារបៀបដែលយើងរាប់ការបន្តទាំងអស់ដែលមានផលិតផលតិចជាងឃេ។

លេខកូដ  

កូដ C ++ ដើម្បីរាប់ការបន្តទាំងអស់ដែលមានផលិតផលតិចជាង K

#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

ការវិភាគស្មុគស្មាញ  

ស្មុគស្មាញពេលវេលា

O (N * K), ពីព្រោះមានរដ្ឋចំនួនពីរដែលមួយជាសន្ទស្សន៍សម្រាប់ធាតុបញ្ចូលហើយមួយទៀតជាផលនៃដែនកំណត់ជាបន្តបន្ទាប់។ ពួកវាមានព្រំដែនខាងលើ N និង K ដូច្នេះភាពស្មុគស្មាញពេលវេលាគឺពហុធា។

ភាពស្មុគស្មាញនៃលំហ

O (N * K), ពីព្រោះយើងបង្កើតតារាងឌី។ ភី។ ឌី។ អេ។ ២ ជាមួយនឹងកោសិកា N * K ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហក៏មានពហុធាផងដែរ។

សូម​មើល​ផង​ដែរ
មេគុណ Binomial