You are viewing a single comment's thread. Return to all comments →
There is a closed form solution that's the sum of a geometric alternating series, and does not require dynamic programming.
Here's the hint: count the number of ways you can construct ALL possible arrays starting from 1, disregarding the x at the end. Then, subtract out the number that end in x.
Since the array starts with 1, at each step the number of ways that end in 1 will be different from the number of ways that end in 2..k
For example, on the first step, we will have (k-1) possible values, and all will be in the range 2..k
Then on the 2nd step, we have (k-1)^2 possible combinations. (k-1) will be 1 and (k-1)^2 - (k - 1) will be in the range 2..k
On the 3rd step, (k-1)^3 total possible combinations. (k-1)^2 - (k-1) are 1, and (k-1)^3 - (k-1)^2 + (k-1) will be 2..k
This gives you an alternating geometric series that you can either compute sequentially in O(n), or find the closed form for and compute in O(log n) (to compute (k-1)^n)