Help me out in this?
@shivammishra20121999
dp[i][v] = number of ways to fill the array up to index i, if x[i] = v.
We treat i = 0 separately. Either x[0] = 0, so we can replace it by anything (i.e dp[0][v] = 1 for all v). Otherwise x[0] = v ≠≠ 0, so that dp[0][v] = 1 is the only allowed value.
Now to the other indices i > 0. If x[i] = 0, we can replace it by any value. However, if we replace it by v, the previous value must be either v-1, v or v+1. Thus the number of ways to fill the array up to i, is the sum of the previous value being v-1, v and v+1. If x[i] = v from the input, only dp[i][v] is allowed (i.e dp[i][j] = 0 if j ≠≠ v). Still dp[i][v] = dp[i-1][v-1] + dp[i-1][v] + dp[i-1][v+1].
The complexity is O ( n ⋅ m )O(n⋅m) with worst-case when x is all zeros.
@shivammishra20121999 i will try because to solve it using this approach consumes my whole day . not sure i will be able to do so. try to solve using this logic .
@himanshu_aswal i am not much confortable with bottom up approach usually i solve through top down approach
@shivammishra20121999 it comes with practise only. try solve from easy problems and then move to harder probelems.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.