Tiling problems [1/2] | Dynamic Programming

[@ayyappahemanth7134]

No other youtuber shown animations about recursions like this. Thank you so much, it helped me understand better!.

[@AlgosWithKartik]

Great videos! Your content is high quality. For interested people a more generic tiling problem is when the grid is of size N*M and tiles of sizes 2 are available, can be solved using dp with bitmask. CSES Problem counting tilings.

[@royalbhati7837]

Your content is also high quality!! keep up the good work!

[@themichaelw]

So well explained. I appreciate all the effort you made to produce this, it greatly reduced the learning time for me (and likely many others). Thanks!

[@mickeynig1]

I am so glad that I found your channel! So randomly on leetcode discussion. Great explanation please keep it up!

[@kintrix007]

Such a good video! Clear explanations and to the point. Just, chef's kiss

[@andresroca9736]

Great man, you have return! I was hoping you were active again. This videos you make are just awesome. Thanks pal. Software Development as it has to be: full of visual imagination and just the necessary code. Subscribed. Muchos Saludos 🤙🏼

[@oleksandrtkach416]

Your videos are amazing! Please continue recording!

[@dinohunter7176]

Nice problem and explanation of the solution. Thanks William!

[@0anant0]

Excellent explanation, as always -- for animation, if you can add arrows to show direction (making recursive call vs returning (unwind, callback) from recursive call) it would be awesome!

[@deepakforyou]

It's like staircase puzzle.. awesome video..

[@0anant0]

Yes, its Fibonacci pattern (jump, climb stairs, paint/rob houses, decode string, etc)

[@ViktorKishankov]

Yes, I’ve also remembered a staircase problem based on this 😉 nice to have another example to this approach

[@prakash_77]

Great explanation and visuals!

[@pallavi9491]

You have the best content. Please make videos on design patterns. Please.

[@faruhjmishenkopetrovich4011]

Oh la la , you're back!Thank you for vid

[@gyi1141]

so amazing super nice quality

[@vinhnghiang1273]

11:28 can anyone please help me why we use n+1 here

[@gradientO]

Explained beautifully

[@DuarteCoelho-td2ci]

Hey, I have a question, how could you do this if the size of the blue block was 3 instead of 2?? Is there any possible way to do it?

[@Jkauppa]

use the style in the probability calculations permutations to determine "how many ways" something can be done, after certain selections

[@Jkauppa]

what for these are used

[@Jkauppa]

why do you calculate different arrangements that can be made from the tiles, instead of the different random placements of the tiles, those are different problems, appearance and the block themselves

[@sachin_yt]

Two things you forgot to mention about: 1. It is same as calculating Fibonacci(n) 2. We don't need a new array using second approach since we canonly store last two previous values i.e. prev1 and prev2, which brings down the space complexity to O(1) 🙂

[@CrAzzyWak]

14:10 - You say that we "can see" that the number of tilings in a column is based on the number of tilings in the previous two, I can feel it, but it is no proof? What is the proof for this?

[@WilliamFiset-videos]

The proof is baked in the recurrence: f(n) = f(n-1) + f(n-2). You can think of n as the column

[@mathuratudu7271]

Your videos are on point.

[@monickverma2944]

this is so good i want to cry

[@TwoVera]

cry on my chest

[@shubhamagarwal2998]

Make more 🔥🔥🔥🔥🙏

[@vasyasmanager2you]

Hello. Can you please make a video explaining the principle and demonstrating the programming application of Blossom algorithm?

[@adnanniazi9954]

To remove an articulation point from a graph we need to ? A: remove an edge B: add an edge C: both a and b D: none of the above

[@5590priyank]

Is it Fibonacci series?

[@lucien5112]

every other dynamic programming KZbinr: yeah you can copy the Fibonacci video, but change it a little so they can't tell William:

[@subee128]

Thanks

[@FranklinChen]

Excellent visualization! You didn't mention "Fibonacci" though :-).

[@andreamengoli4656]

Easter egg

[@avimehenwal]

Hey how do you make such amazing animations and visualizations? So cool

[@SuperShank76]

"we don't need to worry about the uniqueness of tilings" -- this problem would get difficult if we postulated that arrangements that looked the same from left->right and right->left were considered identical.i.e if say BRR were treated same as RRB. You could flip one arrangement to get the other.

[@nonconsensualopinion]

Would we not simply divide our solution by two to remove the symmetry?

[@andreamengoli4656]

Thank you

[@abhisheksuryavanshi9675]

Please make more algorithmic vedios

[@madhukiranattivilli2321]

So f(n) = f(n-1) + f(n-2) in top-down approach, we intend to compute f(5) and reach down in bottom-up approach, we start from f(0) and f(1) and reach to f(5) bottom-up seems much better as we can avoid the stack of recursive function calls, and instead calculate f(2) through f(5) in a loop using DP. So, we achieved time complexity of O(n) -- linear time. However, there is a much better way to complete the calculation f(n) in constant time O(1), using maths formula calculation -- known as binot's formula. If u notice, the recurrence/recursive formula f(n) = f(n-1) + f(n-2) is the formula for fibonacci series, and all we want is to calculate the value of n-th fibonacci number. Here we have f0=1, f1=1, f2=2, f3=3, f4=5, f5=8 f(n) let f(n+1) = k * f(n) f(0) = 1 let f(0) = t -- we generalize the value at each level f(n+1) = kf(n) f(1) = kf(0) = tk f(2) = kf(1) = tk^2 f(3) = kf(2) = tk^3 f(n) = tk^n Let g(n) and h(n) be 2 other fibonacci series, and let f(n) be a sum of those 2 series g(n) = g(n-1) + g(n-2) h(n) = h(n-1) + h(n-2) f(n) = g(n) + h(n) = g(n-1) + g(n-2) + h(n-1) + (n-2) = (g(n-1) + h(n-1)) + (g(n-2) + (n-2)) = f(n-1) + f(n-2) thus, the sum of 2 fibonacci series is also a fibonacci series f(n+1) = kf(n) f(n+2) = f(n+1) + f(n) kf(n+1) = kf(n) + f(n) k^2f(n) = kf(n) + f(n) k^2 - k - 1 = 0 Generalizing the binomial quadratic equation ax^2 + bx + c = 0 x^2 + 2 * x * (b/2a) + (b/2a)^2 = (b/2a)^2 - (c/a) (x + b/2a)^2 = (b^2 - 4ac) / (2a)^2 x + b/2a = +\- sqrt(b^2 - 4ac) / 2a x = (-b +\- sqrt(b^2 - 4ac)) / 2a Substituting... x=k | a=1 | b=-1 | c=-1 k = (1 +\- sqrt5) / 2 Let a = (1 + sqrt5) / 2 b = (1 - sqrt5) / 2 f(n) = tk^n f(n) = g(n) + h(n) let g(n) = gk^n and h(n) = hk^n let's use the 2 possible values of k -- a and b f(n) = g(n) + h(n) f(n) = ga^n + hb^n f(0) = 1 1 = g + h h = 1 - g f(1) = 1 1 = ga + hb 1 = ga + (1 - g)b 1 = g(a - b) + b g = (1 - b) / (a - b) a - b = ( (1 + sqrt5) - (1 - sqrt5) ) / 2 a - b = sqrt5 a + b = ( (1 + sqrt5) + (1 - sqrt5) ) / 2 a + b = 1 1 - b = a g = a/sqrt5 h = 1 - g h = (sqrt5 - a) / sqrt5 h = (a - b - a) / sqrt5 h = -b/sqrt5 f(n) = ga^n + hb^n f(n) = a^n * (a/sqrt5) + b^n * (-b/sqrt5) Hence f(n) = (a^(n+1) - b^(n+1)) / sqrt5 Substituting... f(0) = (a^1 - b^1)/sqrt5 = (a-b)/sqrt5 = sqrt5/sqrt5 = 1 f(1) = (a^2 - b^2) / sqrt5 = (a+b)*(a-b)/sqrt5 = 1*sqrt5/sqrt5 = 1 f(-1) = 0 = (a^0 - b^0)/sqrt5 = (1 - 1)/sqrt5 = 0 f(2) = (a^3 - b^3)/sqrt5 = (a - b) * (a^2 + ab + b^2) / sqrt5 = a^2 + 2ab + b^2 - ab = (a + b)^2 - ab = 1 - ab ab = (1+sqrt5) * (1-sqrt5) / 2^2 = (1^2 - sqrt5^2)/4 = (1-5)/4 = -1 f(2) = 1 - (-1) = 2 - Madhukiran

[@abcd-sf5ur]

but coding that formula might give wrong answers due to precison errors

[@madhukiranattivilli2321]

@@abcd-sf5ur For the range of numbers I checked the int(f(n)) always came correct (f(n) is floating point result)

[@oneepicsaxguy6067]

"let f(n+1) = k * f(n)" How do you assume that this k is always constant for all 'n'. That is how do you assume k = f(1)/f(0) = f(2)/f(1) and so on. I'm aware of this formula for fibonacci numbers but this proof assumes that the ratio of 2 fibonacci numbers is always equal. This ratio slowly approaches a number called the golden ratio but is not constant for every n. Edit: "f(n+1) = f(n) + f(n-1) so f(n+1) > f(n) let f(n+1) = k * f(n)" f(n+1) > f(n) does not imply f(n+1) = k*f(n) Example:- Consider a series of squares. f(1) = 1, f(2) = 4, f(3) = 9 and so on f(n+1) > f(n) always. But this does not mean f(n+1) = k*f(n). For n = 1 this k = 4, for n = 2, this k = 9/4

[@madhukiranattivilli2321]

@@oneepicsaxguy6067 I agree. I too was stuck there. That's the main assumption in the formula generation. Later, in f(n) = g(n) + h(n), we are taking the 2 possible values of k, the golden ratio. alpha = (1 + sqrt5)/2 and beta = (1 - sqrt5)/2 Due to considering the 2 possible values of k, I'm assuming the final formula f(n) = (a^(n+1) - b^(n+1))/sqrt5 may neutralize the impact of the assumption. I see that the formula gives same result as the top-down recursive algorithm and the bottom-up iterative algorithm for any value of n. Please correct me further if u r aware.

[@madhukiranattivilli2321]

@@oneepicsaxguy6067 (2nd msg) I agree with u that k is not constant for every n, where f(n+1) > f(n). Yet, here we are talking only about fibonacci numbers f(n) = f(n-1) + f(n-2). I guess, we shouldn't consider this for squares f(n) = n^2 (the example u used). Comment?

[@abhayrathi284]

YOU ARE GOD.

[@showmickkar7793]

1st!