Array Description

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Example:

Input:  n = 3, m = 5, a = {2, 0, 2}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int arrayDescription(int n, int m, vector<int> &a)
{

    int dp[n][m + 1];

    //fill with zeros
    memset(dp, 0, sizeof dp);

    //if first element is zero
    if (a[0] == 0)
    {
        for (int i = 1; i <= m; i++)
            dp[0][i] = 1;
    }
    else
    {
        dp[0][a[0]] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        if (a[i] == 0)
        {
            for (int j = 1; j <= m; j++)
            {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                if (j > 1)
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
                if (j < m)
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
            }
        }
        else
        {
            int j = a[i];
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
            if (j > 1)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
            if (j < m)
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = (ans + dp[n - 1][i]) % MOD;
    return ans;
}

int main()
{

    int n = 3, m = 5;

    vector<int> a = {2, 0, 2};

    cout << arrayDescription(n, m, a) << "\n";

    return 0;
}