Tiling problems [1/2] | Dynamic Programming
Вставка
- Опубліковано 15 лип 2024
- An introduction on how to solve tiling problems using dynamic programming
Next video:
• Tiling problems [2/2] ...
Project Euler practice problems:
projecteuler.net/problem=114
projecteuler.net/problem=115
projecteuler.net/problem=116
projecteuler.net/problem=117
Algorithms code repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/algor...
Website:
www.williamfiset.com
Audio intro/outro composed by Richard Saney (rnsaney@gmail.com)
0:00 Intro
1:23 Top-down approach
3:47 Recursion tree
7:06 Recursive approach code
7:40 Repeating subtrees
8:39 Recursion tree with caching
11:07 Recursive implementation with caching
12:37 Bottom-up approach
15:08 Bottom-up (iterative) implementation
15:50 Related tiling problems
![Tiling problems [2/2] | Dynamic Programming](http://i.ytimg.com/vi/L1x3an2pl3U/mqdefault.jpg)
![Tiling problems [2/2] | Dynamic Programming](/img/tr.png)
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.
Your content is also high quality!!
keep up the good work!
No other youtuber shown animations about recursions like this. Thank you so much, it helped me understand better!.
I am so glad that I found your channel! So randomly on leetcode discussion. Great explanation please keep it up!
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 🤙🏼
Such a good video! Clear explanations and to the point. Just, chef's kiss
Your videos are amazing! Please continue recording!
Great explanation and visuals!
Nice problem and explanation of the solution. Thanks William!
Oh la la , you're back!Thank you for vid
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!
Explained beautifully
Your videos are on point.
so amazing super nice quality
You have the best content. Please make videos on design patterns. Please.
It's like staircase puzzle.. awesome video..
Yes, its Fibonacci pattern (jump, climb stairs, paint/rob houses, decode string, etc)
Yes, I’ve also remembered a staircase problem based on this 😉 nice to have another example to this approach
Make more 🔥🔥🔥🔥🙏
Thanks
Thank you
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) 🙂
Hey how do you make such amazing animations and visualizations? So cool
this is so good i want to cry
cry on my chest
Hello. Can you please make a video explaining the principle and demonstrating the programming application of Blossom algorithm?
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
use the style in the probability calculations permutations to determine "how many ways" something can be done, after certain selections
what for these are used
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
Is it Fibonacci series?
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?
11:28 can anyone please help me why we use n+1 here
"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.
Would we not simply divide our solution by two to remove the symmetry?
Please make more algorithmic vedios
Excellent visualization! You didn't mention "Fibonacci" though :-).
Easter egg
YOU ARE GOD.
every other dynamic programming UA-camr: yeah you can copy the Fibonacci video, but change it a little so they can't tell
William:
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?
The proof is baked in the recurrence: f(n) = f(n-1) + f(n-2). You can think of n as the column
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
but coding that formula might give wrong answers due to precison errors
@@abcd-sf5ur For the range of numbers I checked the int(f(n)) always came correct (f(n) is floating point result)
"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
@@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.
@@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?
1st!