Link: https://cses.fi/problemset/task/1746/
State: dp[i][k] where it stores the count of valid arrays ending at i with value k
Transition:
if v[i] == k && v[i] != 0
dp[i][k] = dp[i-1][k-1]+dp[i-1][k]+dp[i-1][k+1]
else
iterate through all possible k for 0 which is [1, m]
Base Case:
if v[0] = 0 then increment by 1 for for all i in [1,m], dp[0][i] = 1
otherwise dp[0][v[0]] = 1
Final Subproblem:
Sum over all values of dp[n-1]
for (auto x : dp[n - 1]) {
ans = (ans + x) % mod;
}Final Code:
void solve() {
int n, m;
cin >> n >> m;
vi v(n);
in(v);
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
int mod = 1e9 + 7;
if (v[0] == 0) {
for (int i = 1; i <= m; i++) {
dp[0][i] = 1;
}
} else {
dp[0][v[0]] = 1;
}
for (int i = 1; i < n; i++) {
if (v[i] == 0) {
for (int j = 1; j <= m; j++) {
for (int x : {-1, 0, 1}) {
if (j + x < 0 || j + x > m)
continue;
dp[i][j] = (dp[i][j] + dp[i - 1][j + x]) % mod;
}
}
} else {
int j = v[i];
for (int x : {-1, 0, 1}) {
if (j + x < 0 || j + x > m)
continue;
dp[i][j] = (dp[i][j] + dp[i - 1][j + x]) % mod;
}
}
}
ll ans = 0;
for (auto x : dp[n - 1]) {
ans = (ans + x) % mod;
}
cout << ans << '\n';
}