Ҳама пайдарпайҳоро ҳисоб кунед, ки маҳсулашон камтар аз К бошад  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад ByteDance Пойтахт Яке аз CodeNation Хиштҳо Expedia Yandex
тартиботи ҳарбӣ Барномарезии динамикӣ

Масъалаи "Ҳисоб кардани ҳамаи пайдарпаҳо, ки ҳосилашон камтар аз K аст" мегӯяд, ки ба шумо массиви бутун дода мешавад. Акнун шумораи пайдарпайҳоеро ёбед, ки ҳосилашон аз вуруди додашудаи K камтар бошад.

мисол  

Ҳама пайдарпайҳоро ҳисоб кунед, ки маҳсулашон камтар аз К бошад

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

Шарҳ

11 пайдарпай вуҷуд дорад, ки ҳосилашон камтар аз k (= 8) дода шудааст. Пас аз он дар тасвири боло нишон дода шудааст.

усул  

Мушкилот ба мо пайдарпайии бутунро пешниҳод кард ва адади К., пас ба мо гуфта мешавад, ки шумораи пайдарпаҳоеро, ки ҳосилашон аз K камтар аст, пайдо кунем. Усули соддалавҳона ҳамеша ин тавлид кардани пайдарпаӣ ва сипас санҷидани он аст, ки оё пайдарпаии тавлидшуда шароити моро қонеъ мекунад ё не?

Ин ҳалли соддалавҳона бешубҳа аз мӯҳлати мо зиёдтар хоҳад шуд. Ҳамин тавр, мушкилот дар доираи маҳдудияти вақти муайян ҳал карда мешавад. Мо бояд истифода барем Барномарезии динамикӣ. Пас, дар ин ҷо мо массиви воридшударо убур хоҳем кард. Ҳангоми гузариш мо ҷадвали ҲД-ро ҳамзамон пур мекунем. Мо барои ин мушкилоти DP ду ҳолат дорем, аввал маҳсулот то ба имрӯз ва дуюм индекс барои массиви вурудӣ мебошад. Мо аз маҳсулот оғоз мекунем ва месанҷем, ки оё мо метавонем натиҷаи заруриро бо рақамҳо / элементҳо аз массиви вуруд ба даст орем.

ҳамчунин нигаред
Максимум 69 Ҳалли рақами Leetcode

Чашмаки масси dp мо dp [i] [j] миқдори пайдарпаҳоеро ифода мекунад, ки ҳосилашон камтар аз i мебошанд ва бо истифодаи унсурҳои j аввали вуруд ба вуҷуд омадаанд. Пас, барои ёфтани dp [i] [j], мо аз dp [i / a [j]] [j] ва dp [i] [j-1] вобастаем. Пас, агар a [i]> i, гирифтани ин унсур ба пайдарҳам маънои онро дорад, ки худи [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

Рамзи Java барои ҳисоб кардани ҳамаи пайдарпаҳое, ки маҳсулашон камтар аз 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 доранд, аз ин рӯ мураккабии вақт полиномия аст.

Мураккабии фазо

О (N * K), зеро мо ҷадвали 2D DP бо ҳуҷайраҳои N * K сохтем. Ҳамин тариқ, мураккабии фазо низ полиномия аст.

ҳамчунин нигаред
Коэффитсиенти биномӣ