ນັບທຸກໆເຫດການທີ່ມີຜະລິດຕະພັນຕໍ່າກວ່າ K


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ByteDance Capital One ລະຫັດປະເທດ ຖານຂໍ້ມູນ Expedia Yandex
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ບັນຫາ“ ນັບທັງ ໝົດ ຕໍ່ມາທີ່ມີຜະລິດຕະພັນຕໍ່າກວ່າ K” ລະບຸວ່າທ່ານຖືກມອບໃຫ້ຫລາຍໆໂຕ. ດຽວນີ້ຊອກຫາ ຈຳ ນວນຂອງການຕິດຕໍ່ກັນທີ່ມີຜະລິດຕະພັນ ໜ້ອຍ ກວ່າວັດສະດຸປ້ອນເຂົ້າ K.

ຍົກຕົວຢ່າງ

ນັບທຸກໆເຫດການທີ່ມີຜະລິດຕະພັນຕໍ່າກວ່າ K

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

ຄໍາອະທິບາຍ

ມີ 11 ວິທີຕໍ່ມາເຊິ່ງມີຜະລິດຕະພັນ ໜ້ອຍ ກວ່າ k (= 8). ການຕິດຕໍ່ກັນແມ່ນສະແດງຢູ່ໃນຮູບຂ້າງເທິງ.

ວິທີການ

ບັນຫາດັ່ງກ່າວໄດ້ສະ ໜອງ ໃຫ້ພວກເຮົາມີ ລຳ ດັບຂອງຕົວເລກ, ແລະຕົວເລກ K. ຫຼັງຈາກນັ້ນພວກເຮົາຖືກບອກໃຫ້ຊອກຫາ ຈຳ ນວນຂອງການຕິດຕໍ່ກັນທີ່ມີຜະລິດຕະພັນ ໜ້ອຍ ກ່ວາ K. ດັ່ງນັ້ນ, ທຸກຄັ້ງທີ່ພວກເຮົາປະຕິບັດຕໍ່ກັບການຕິດຕໍ່, ການຍ່ອຍ, ຫຼື subarrays. ວິທີການທີ່ໂງ່ຈ້າແມ່ນສະເຫມີໄປທີ່ຈະຜະລິດລໍາດັບເຫຼົ່ານີ້ແລະຫຼັງຈາກນັ້ນກວດເບິ່ງວ່າລໍາດັບທີ່ຜະລິດໄດ້ຕອບສະ ໜອງ ເງື່ອນໄຂຂອງພວກເຮົາຫຼືບໍ່?

ການແກ້ໄຂທີ່ໂງ່ຈ້ານີ້ແນ່ນອນຈະເກີນ ກຳ ນົດເວລາຂອງພວກເຮົາ. ສະນັ້ນເພື່ອແກ້ໄຂບັນຫາພາຍໃຕ້ຂໍ້ ຈຳ ກັດທີ່ ກຳ ນົດໄວ້. ພວກເຮົາ ຈຳ ເປັນຕ້ອງໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ. ດັ່ງນັ້ນໃນທີ່ນີ້ພວກເຮົາຈະຂ້າມຜ່ານແຖວເຂົ້າ. ໃນຊ່ວງເວລາທີ່ມີຄວາມເສົ້າສະຫລົດໃຈ, ພວກເຮົາຈະຕື່ມຂໍ້ມູນໃສ່ໂຕະ DP ພ້ອມໆກັນ. ພວກເຮົາມີສອງລັດ ສຳ ລັບບັນຫາ DP ນີ້, ທຳ ອິດແມ່ນຜະລິດຕະພັນຈົນເຖິງປະຈຸບັນແລະອັນທີສອງແມ່ນດັດສະນີ ສຳ ລັບແຖວເຂົ້າ. ພວກເຮົາເລີ່ມຕົ້ນກັບຜະລິດຕະພັນແລະກວດເບິ່ງວ່າພວກເຮົາສາມາດໄດ້ຮັບຜົນທີ່ຕ້ອງການກັບຕົວເລກ / ສ່ວນປະກອບຕ່າງໆຈາກແຖວອາຫານເຂົ້າ.

dp array cell ຂອງພວກເຮົາ dp [i] [j] ສະແດງ ຈຳ ນວນຂອງການຕິດຕໍ່ກັນທີ່ມີຜະລິດຕະພັນ ໜ້ອຍ ກວ່າ i ແລະຖືກສ້າງຕັ້ງຂຶ້ນໂດຍ ນຳ ໃຊ້ j ອົງປະກອບ ທຳ ອິດຂອງວັດສະດຸປ້ອນ. ດັ່ງນັ້ນ ສຳ ລັບການຊອກຫາ dp [i] [j], ພວກເຮົາແມ່ນຂື້ນກັບ dp [i / a [j]] [j] ແລະ dp [i] [j-1]. ສະນັ້ນຖ້າ a [i]> i, ການເອົາສ່ວນປະກອບນີ້ເຂົ້າໄປໃນພາຍຫຼັງກໍ່ ໝາຍ ຄວາມວ່າ a [i] ເອງກໍ່ໃຫຍ່ກວ່າ K. ສະນັ້ນ, ອົງປະກອບນີ້ຈະບໍ່ຖືກພິຈາລະນາ. ນັ້ນແມ່ນວິທີທີ່ພວກເຮົານັບການຕິດຕາມທັງ ໝົດ ທີ່ມີຜະລິດຕະພັນ ໜ້ອຍ ກ່ວາ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N * K), ເນື່ອງຈາກວ່າມີສອງລັດ ໜຶ່ງ ຄືດັດຊະນີ ສຳ ລັບເຄື່ອງປ້ອນຂໍ້ມູນແລະອີກ ໜຶ່ງ ລັດແມ່ນຜະລິດຕະພັນຂອງຂີດ ຈຳ ກັດຕໍ່ມາ. ພວກມັນມີ N ແລະ K ທີ່ຜູກມັດດ້ານເທິງ, ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາຈຶ່ງມີຫຼາຍຂີດ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N * K), ເພາະວ່າພວກເຮົາສ້າງຕາຕະລາງ 2D DP ທີ່ມີ N * K ຈຸລັງ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງມີຫຼາຍຮູບແບບ.