We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The editorial is very complicated, so this is how I solved this problem:
Let dp[i][j] be the number of ways to make an array of length i ending with j. Then dp[1][1] is 1 and dp[1][2], dp[1][3]... are 0, because the array always starts with 1. Now dp[i][j] is the sum of all the elements dp[i-1][1..k] without dp[i-1][j](because two consecutive numbers must be different). However if you do it on paper you will see that values are the same for j>1. Therefore only calculate dp[i][1] and dp[i][2].
Hope you can figure it out from here :)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Construct the Array
You are viewing a single comment's thread. Return to all comments →
The editorial is very complicated, so this is how I solved this problem:
Let dp[i][j] be the number of ways to make an array of length i ending with j. Then dp[1][1] is 1 and dp[1][2], dp[1][3]... are 0, because the array always starts with 1. Now dp[i][j] is the sum of all the elements dp[i-1][1..k] without dp[i-1][j](because two consecutive numbers must be different). However if you do it on paper you will see that values are the same for j>1. Therefore only calculate dp[i][1] and dp[i][2]. Hope you can figure it out from here :)