leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

find_stable_binary_arr2.c (2419B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 3130. Find All Possible Stable Binary Arrays II
#include "leetcode.h"

/*
 * you are given 3 positive integers 'zero', 'one', and 'limit'. a binary array
 * 'arr' is called stable is the number of occurences of 0 in 'arr' is exactly
 * 'zero', the number of occurences of  1 in 'arr' is exactly 'one', and each
 * subarray of 'arr' with a size greater than 'limit' must contain 0 and 1.
 * return the total number o stable binary arrays. since the answer may be very
 * large, return it modulo 10^9+7.
 */

static int mod = 1e9 + 7;

int ***memo_init(int zero, int one) {
  int ***memo = (int ***)malloc((zero + 1) * sizeof(int **));
  for (int i = 0; i <= zero; ++i) {
    memo[i] = (int **)malloc((one + 1) * sizeof(int *));
    for (int j = 0; j <= one; ++j) {
      memo[i][j] = (int *)malloc(2 * sizeof(int));
      memo[i][j][0] = memo[i][j][1] = -1;
    }
  }
  return memo;
}

void memo_free(int zero, int one, int ***memo) {
  for (int i = 0; i <= zero; ++i) {
    for (int j = 0; j <= one; ++j)
      free(memo[i][j]);
    free(memo[i]);
  }
  free(memo);
}

int dp(int zero, int one, int prev_bit, int limit, int ***memo) {
  if (!zero)
    return (prev_bit || one > limit) ? 0 : 1;
  else if (!one)
    return (prev_bit == 1 || zero > limit) ? 0 : 1;
  if (memo[zero][one][prev_bit] == -1) {
    int res = 0;
    if (!prev_bit) {
      res = (dp(zero - 1, one, 0, limit, memo) +
             dp(zero - 1, one, 1, limit, memo)) %
            mod;
      if (zero > limit)
        res = (res - dp(zero - limit - 1, one, 1, limit, memo) + mod) % mod;
    } else {
      res = (dp(zero, one - 1, 0, limit, memo) +
             dp(zero, one - 1, 1, limit, memo)) %
            mod;
      if (one > limit)
        res = (res - dp(zero, one - limit - 1, 0, limit, memo) + mod) % mod;
    }
    memo[zero][one][prev_bit] = res % mod;
  }
  return memo[zero][one][prev_bit];
}

int numberOfStableArrays(int zero, int one, int limit) {
  int ***memo = memo_init(zero, one);
  int ans =
      (dp(zero, one, 0, limit, memo) + dp(zero, one, 1, limit, memo)) % mod;
  memo_free(zero, one, memo);
  return ans;
}

int main() {
  int r1 = numberOfStableArrays(1, 1, 2);
  int r2 = numberOfStableArrays(1, 2, 1);
  int r3 = numberOfStableArrays(3, 3, 2);
  printf("%d\n", r1); // expect: 2
  assert(r1 == 2);
  printf("%d\n", r2); // expect: 1
  assert(r2 == 1);
  printf("%d\n", r3); // expect: 14
  assert(r3 == 14);
}