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

  • samer_ghaly2017
     + 0 comments

    JAVA: --> public static final int MOD = 1000000007; static long[][] memo; static int x, n, k;

         public static long dp(int u, int isX) {
    if (u == n - 1) return isX == 1 ? 1 : 0;
    if (memo[u][isX] != -1) return memo[u][isX];
    long ans = 0;
    if (isX == 1 || (u == 0 && x == 1)) {
        ans += (k - 1) * dp(u + 1, 0);
    } else {
        ans += (k - 2) * dp(u + 1, 0);
        ans %= MOD;
        ans += dp(u + 1, 1);
    }
    ans %= MOD;
    return memo[u][isX] = ans;
}

public static long countArray(int n, int k, int x) {
    Result.n = n;
    Result.k = k;
    Result.x = x;
    memo = new long[n][2];
    for (int i = 0; i < n; i++)
        Arrays.fill(memo[i], -1);
    return dp(0, 0) % MOD;

}