Explanation:

1, say we have n == 7, the number 1 can replace any of the 2 to 7, and each of that replacement is identical, so after we calculate the result, just multiply by 6.

2, now say we use 1 to replace 4, then for the number 4 alone, we have two options, either put 4 back to its position in 2, 3, 4, 5, 6, 7 which should the result of 6 numbers -> last result, or simply be disappeared, then we are left with 5 numbers 2, 3, 5, 6, 7 -> lastLast result. Then just add the two results together and multiply by 6, you will get the correct number

3, why DP? last is the result we calculated for k - 1 numbers, and lastLast is the result we calculated for k - 2 numbers