Count the Number of Ideal Arrays | Leetcode 2338

class Solution {
    #define ll long long

    ll count[15][10005];
    ll prefix_sum[15][10005];
    ll options[15];
    int MOD = 1e9+7;

    void countUniqueSequences(int curr,int idx,int& maxValue){
        options[idx]+=1;
        for(int j=2; curr*j <= maxValue; ++j)
            countUniqueSequences(curr*j,idx+1,maxValue);
    }
public:
    int idealArrays(int n, int maxValue) {
        //Set default value to 0 for all arrays
        memset(count,0,sizeof(count));
        memset(prefix_sum,0,sizeof(prefix_sum));
        memset(options,0,sizeof(options));

        //Pre-fill 1st row
        for(int i=1;i<=10000;++i){
            count[1][i]=1;
            prefix_sum[1][i]=i;
        }

        //Fill the count table
        for(int i=2;i<=14;++i){
            for(int j=i;j<=10000;++j){
                count[i][j] = prefix_sum[i-1][j-1];
                prefix_sum[i][j] = count[i][j] + prefix_sum[i][j-1];
                count[i][j] %= MOD;
                prefix_sum[i][j] %= MOD;
            }
        }

        //Calculate options
        for(int i=1;i<=maxValue;++i)
            countUniqueSequences(i,1,maxValue);

        //Count total ideal arrays
        ll ans = 0;
        ll ways;
        for(int i=1;i<=14;++i){
            ways =  count[i][n] * options[i];
            ways %= MOD;
            ans += ways;
            ans %= MOD;
        }
        return ans;
    }
};
/*
//JAVA
class Solution {
    private static final int MOD = (int)1e9 + 7;
    private long[][] count;
    private long[][] prefixSum;
    private long[] options;

    private void countUniqueSequences(int curr, int idx, int maxValue) {
        options[idx]++;
        for (int j = 2; curr * j <= maxValue; ++j) {
            countUniqueSequences(curr * j, idx + 1, maxValue);
        }
    }

    public int idealArrays(int n, int maxValue) {
        count = new long[15][10005];
        prefixSum = new long[15][10005];
        options = new long[15];

        // Pre-fill 1st row
        for (int i = 1; i <= 10000; ++i) {
            count[1][i] = 1;
            prefixSum[1][i] = i;
        }

        // Fill the count table
        for (int i = 2; i <= 14; ++i) {
            for (int j = i; j <= 10000; ++j) {
                count[i][j] = prefixSum[i - 1][j - 1];
                prefixSum[i][j] = (count[i][j] + prefixSum[i][j - 1]) % MOD;
                count[i][j] %= MOD;
            }
        }

        // Calculate options
        for (int i = 1; i <= maxValue; ++i) {
            countUniqueSequences(i, 1, maxValue);
        }

        // Count total ideal arrays
        long ans = 0;
        for (int i = 1; i <= 14; ++i) {
            long ways = (count[i][n] * options[i]) % MOD;
            ans = (ans + ways) % MOD;
        }
        return (int)ans;
    }
}

#Python
class Solution:
    MOD = 10**9 + 7

    def idealArrays(self, n: int, maxValue: int) -> int:
        count = [[0] * 10005 for _ in range(15)]
        prefix_sum = [[0] * 10005 for _ in range(15)]
        options = [0] * 15

        def countUniqueSequences(curr, idx, maxValue):
            options[idx] += 1
            j = 2
            while curr * j <= maxValue:
                countUniqueSequences(curr * j, idx + 1, maxValue)
                j += 1

        # Pre-fill 1st row
        for i in range(1, 10001):
            count[1][i] = 1
            prefix_sum[1][i] = i

        # Fill the count table
        for i in range(2, 15):
            for j in range(i, 10001):
                count[i][j] = prefix_sum[i - 1][j - 1]
                prefix_sum[i][j] = (count[i][j] + prefix_sum[i][j - 1]) % self.MOD
                count[i][j] %= self.MOD

        # Calculate options
        for i in range(1, maxValue + 1):
            countUniqueSequences(i, 1, maxValue)

        # Count total ideal arrays
        ans = 0
        for i in range(1, 15):
            ways = (count[i][n] * options[i]) % self.MOD
            ans = (ans + ways) % self.MOD
        return ans
*/