Tiling problem 2 need intution for dp approach

#1

im getting tle for the recursive approach.
My code

#2

Hello @Prankur-Tewari-2574939259288733,

It is the same as recursive approach.
Entirely the same code.
All you have to do is memorization in the logic.

How would you do that?

  1. Just have a linear memorization array say mp[i],
    where i will specify the length of the region to be tilled

  2. Initialize this array with all -1.

  3. Add an extra case for looking up from the memorization array.
    i.e. when mp[i]!=-1 i.e. when you have already calculated the number of ways for i length of the region.
    just return mp[i]

  4. mp[i] will store the number of ways to tile ixm area.

You can refer to the following code for better understanding:

Hope, this would help.
Give a like if you are satisfied.

1 Like