Count the Number of Ideal Arrays — LeetCode 2338 Python Solution

The problem

You are given two integers n and maxValue, which are used to describe an ideal array. A 0-indexed integer array arr of length n is considered ideal if the following conditions hold: Every arr[i] is a value from 1 to maxValue, for 0 <= i < n.

Example

Input

n = 2, maxValue = 5

Output

10

Explanation

The following are the possible ideal arrays:

Python solution

class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        @cache
        def dfs(i, cnt):
            res = c[-1][cnt - 1]
            if cnt < n:
                k = 2
                while k * i <= maxValue:
                    res = (res + dfs(k * i, cnt + 1)) % mod
                    k += 1
            return res

        c = [[0] * 16 for _ in range(n)]
        mod = 10**9 + 7
        for i in range(n):
            for j in range(min(16, i + 1)):
                c[i][j] = 1 if j == 0 else (c[i - 1][j] + c[i - 1][j - 1]) % mod
        ans = 0
        for i in range(1, maxValue + 1):
            ans = (ans + dfs(i, 1)) % mod
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2338. Count the Number of Ideal Arrays is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems