Editorial (C++)

Explanation

Let's define $\text{dp}[i][j]$ as the number of ways to fill the first $i$ elements of the array, such that $a_i = j$.

Base case: if $x_1 = 0$, then the first element is unknown and can be anything from $1$ to $m$, so $\text{dp}[1][j] = 1$ for all $j$. Otherwise, the first element is fixed, so $\text{dp}[1][x_1] = 1$ and all other $\text{dp}[1][j] = 0$.

For $i > 1$, since adjacent elements differ by at most $1$, $a_i = j$ is possibly only if $a_{i-1}$ is $j-1$, $j$, or $j+1$:

We can use the same idea seen in Grid Paths, where a trap cell forces $dp[x][y] = 0$ since no path can end there. Then, we set $\text{dp}[i][j] = 0$ whenever index $i$ is fixed to a value other than $j$, since no valid array can have $a_i = j$ in that case.

We compute the final answer by summing $\text{dp}[n][j]$ over all $j$ from $1$ to $m$.

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
import java.io.*;
import java.util.*;

public class ArrayDesc {
	public static final int MOD = (int)1e9 + 7;
	public static void main(String args[]) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(r.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());