К-ээс бага бүтээгдэхүүнтэй бүх дарааллыг тоол


Хэцүү байдлын түвшин Easy
Байнга асуудаг БайтДанс Капитал Нэг CodeNation Өгөгдлийн сан Expedia Yandex
Array Динамик програмчлал

“K-ээс бага бүтээгдэхүүнтэй бүх дэд дарааллыг тоолох” гэсэн асуудалд танд бүхэл тоон массивыг өгч байгаа гэсэн үг юм. Одоо өгөгдсөн K оролтоос бага бүтээгдэхүүнтэй дарааллын тоог олоорой.

Жишээ нь

К-ээс бага бүтээгдэхүүнтэй бүх дарааллыг тоол

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

Тайлбар

K (= 11) өгөгдсөн хэмжээнээс бага бүтээгдэхүүнтэй 8 дараалал байдаг. Дараах зурвасуудыг дээрх зураг дээр харуулав.

арга барил

Асуудал нь бүхэл тоонуудын дарааллыг бидэнд өгсөн бөгөөд бүхэл бүтэн K-ийг өгсний дараа K-ээс бага үржвэр бүхий дарааллын тоог олохыг бидэнд хэлье. Гэнэн хандлага бол эдгээр дарааллыг бий болгож дараа нь үүссэн дараалал нь бидний нөхцөл байдалд нийцэж байгаа эсэхийг шалгах явдал юм.

Энэхүү гэнэн шийдэл нь бидний тогтоосон хугацааг давах нь дамжиггүй. Тиймээс тухайн цаг хугацааны хязгаарлалтаар асуудлыг шийдвэрлэх. Бид ашиглах шаардлагатай байна Динамик програмчлал. Тиймээс бид оролтын массивыг дайран өнгөрөх болно. Тэмцээний үеэр бид АН-ын хүснэгтийг нэгэн зэрэг дүүргэх болно. Энэ АН-ын асуудалд бид хоёр төлөвтэй байна, нэгдүгээрт өнөөг хүртэлх бүтээгдэхүүн, хоёр дахь нь оролтын массивын индекс юм. Бид бүтээгдэхүүнээс эхэлж оролтын массиваас тоо / элементийн тусламжтайгаар шаардлагатай үр дүнг авч чадах эсэхийг шалгана.

Манай dp массив нүд dp [i] [j] нь i-ээс бага бүтээгдэхүүнтэй оролтын эхний j элементүүдийг ашиглан үүссэн дарааллын тоог илэрхийлнэ. Тиймээс dp [i] [j] -ийг олохын тулд бид dp [i / a [j]] [j] ба dp [i] [j-1] -ээс хамааралтай болно. Хэрэв a [i]> i бол энэ элементийг дараалалд оруулснаар a [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-ээс бага бүтээгдэхүүн бүхий бүх дарааллыг тоолох 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N * K), Учир нь нэг нь оролтын массивын индекс, нөгөө нь оролтын хязгаарын үржвэр болох хоёр төлөв байдаг. Тэдгээр нь дээд хязгаар N ба K тул цаг хугацааны нарийн төвөгтэй байдал нь олон гишүүнт юм.

Сансрын нарийн төвөгтэй байдал

O (N * K), Учир нь бид 2 * DP хүснэгтийг N * K нүдээр бүтээсэн. Тиймээс орон зайн нарийн төвөгтэй байдал нь бас олон гишүүнт юм.