Given an integer K, we have to construct an array of length N in such a way that, first element is always 1 and last element is always X, another integer given as input.
Each element in the array must be [1, K] and the adjacent elements must not be the same.
We have to find out the number of ways to construct such arrays.
N = 4
K = 3
X = 2
ans = 3
[1, 2, 3, 2]
[1, 2, 1, 2]
[1, 3, 1, 2]
We can try to visualise the construction of the array in the form of a tree.
Consider the tree below for the above example:
At each level, we branch out to form a possible valid array value. The blue circles, represent the array ending that are equal to X, thus valid and the green ones are invalid.
a be the array to represent in the number of valid arrays of length i and
b represent the number of invalid arrays of length i.
We can derive the following overlapping subproblems in the problem.
1. a[i] = b[i-1]
This makes sense as, if we can make M arrays of length i-1 that are invalid then the same number of arrays can be made of length i that are valid. Just append the valid number at the end.
2. b[i] = (a[i-1] * (k-1)) + (b[i-1] * (k-2))
First part says, if the last number was a valid array ending, then we have k-1 numbers to use.
Second part says, if the last number was one of the invalid numbers, then we have k-2 numbers to use, 1 invalid and 1 valid numbers have to be subtracted.
a[n-1] should give us the answer.