[Leetcode] 2338. Count the Number of Ideal Arrays (tbc prime?)

https://leetcode.com/problems/count-the-number-of-ideal-arrays/description/?envType=daily-question&envId=2025-04-22

initial

omg i rly struggled with just the basic dp

We can think of dp cuz previous array like lets say [1], which is our base case, can be sued for length =2 like [1,1] or [1,2] by appending number from 1 to maxValue+1. If we can divide current number by the previousValue from 1 to current number, we add that to our current dp value.

dp[current_value][length] = sum(dp[previous_value][length - 1])
for all 1 <= previous_value <= maxValue
such that current_value % previous_value == 0.

Once we fill up dp table, the last column of each row holds our answer values so we sum them up.

sol

but still tle even tho its dp dafuq

class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        dp = [[0 for _ in range(n+1)] for _ in range(maxValue+1)]
        MOD = 10**9 + 7

        # Base case: length 1
        for i in range(1,maxValue+1):
            dp[i][1]=1
        for length in range(2,n+1):
            for current in range(1,maxValue+1):
                for previous in range(1, current+1):
                    if current%previous==0:
                        dp[current][length] = (dp[current][length]+ dp[previous][length-1])%MOD
        return sum(dp[i][length] for i in range(1,maxValue+1)) % MOD

i dont get this sol. It is using some prime factor crap

import math
from functools import lru_cache
class Solution:
    def idealArrays(self, n: int, mx: int) -> int:

        @lru_cache(None)
        def gen(k):
            return math.comb(n - 1, k - 1)

        @lru_cache(None)
        def dp(cur, l):
            res = gen(l)
            nxt = cur * 2
            if l == n or nxt > mx:
                return res
            while nxt <= mx:
                res += dp(nxt, l + 1)
                nxt += cur
            return res

        return sum([dp(i, 1) for i in range(1, mx + 1)]) % (10 ** 9 + 7)

complexity

time is The dominant factor in the time complexity is the three nested loops. Therefore, the overall time complexity of your first DP solution is O(n * maxValue^2).

space is the dp table of maxValue * n.