We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Construct the Array
  5. Discussions

Construct the Array

  • theawesomew
     + 0 comments
    NUM = 10**9+7

def countArray(n, k, x):
    dp = [[0 for _ in range(2)] for _ in range(n+1)]
    
    # dp[length][ends in x]
    
    dp[2][0] = k - 2 if x != 1 else k - 1
    dp[2][1] = 1 if x != 1 else 0
    
    for i in range(3, n+1):
        dp[i][0] = ((((k-2) % NUM) * (dp[i-1][0] % NUM)) % NUM + (((k-1) % NUM) * (dp[i-1][1] % NUM)) % NUM) % NUM
        dp[i][1] = dp[i-1][0] % NUM
    
    return dp[n][1] % NUM

    My initial solution - which consumed too much memory - involved computing the number of arrays that could be constructed that concluded with a specific number l but, at its limit it creates a memoisation array of size 4 x 10¹⁰ bytes which is... a bit too much RAM usage. However, ultimately all that matters is whether or not it ended with x or not.