Help me out in this?

#1

https://cses.fi/problemset/task/1746

#2

@mr.encoder are u there can you tell me how to approach this throgh recursion?

#3

Hey @shivammishra20121999 make a 2D dp array in which
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].
#4

@mr.encoder can you explain me with top down approach?

#5

I don’t have an idea about top down for this problem. I won’t be able to help you with that

#6

@mr.encoder bro how one can came directly with bottom up dp approach without recursion?

#7

I have approached this problem by reading an editorial. It was bottom up. So that’s why I told you the bottom up approach

#8

@mr.encoder
see i follow this pattern to solve dp problem
recursive ->top down ->bottom up
approach ?
for me it is diificult to understand the bottom up code ?

#9

It’s the ideal approach bro, as you know both sides which are top down and bottom up. So in some problem, you will get an edge using bottom up and in some top down. By edge I meant, getting intuition.

#10

@mr.encoder i will try once to design recursive code for this

#11

Yes, and if you won’t be able to do it you can ask for help as some better TA will help you for sure in this :slight_smile:

#12

@mr.encoder can you forward it to some others ta who can help in this?

#13

It’s already in the live doubt portal. Someone will soon reply to you on this :slight_smile: