Categories
Video

Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges



Learn how to use Dynamic Programming in this course for beginners. It can help you solve complex programming problems, such as those often seen in programming interview questions about data structures and algorithms.

This course was developed by Alvin Zablan from Coderbyte. Coderbyte is one of the top websites for technical interview prep and coding challenges.

🔗 Check out the Coderbyte channel: https://www.youtube.com/channel/UCOJtQcnBnIy4LERo6vkrItg
🔗 Improve your coding and interview skills: https://coderbyte.com/member?promo=janpromo4351&utm_source=FCC&utm_medium=Video&utm_campaign=promo&utm_content=Dynamic%20Programming (NOT an affiliate link)

This course uses images and animations to help you visualize problems and important concepts. After understanding problems conceptually, you will learn how to solve them in JavaScript using Dynamic Programming. Even though JavaScript is used in this course, you will learn concepts and knowledge that you can apply to other programming languages.

⭐️ Course Contents ⭐️
⌨️ (00:00:00) course introduction
⌨️ (00:03:30) fib memoization
⌨️ (00:38:39) gridTraveler memoization
⌨️ (01:04:52) memoization recipe
⌨️ (01:09:56) canSum memoization
⌨️ (01:29:29) howSum memoization
⌨️ (01:52:06) bestSum memoization
⌨️ (02:12:45) canConstruct memoization
⌨️ (02:38:36) countConstruct memoization
⌨️ (02:47:30) allConstruct memoization
⌨️ (03:10:53) fib tabulation
⌨️ (03:22:17) gridTraveler tabulation
⌨️ (03:34:32) tabulation recipe
⌨️ (03:37:59) canSum tabulation
⌨️ (03:53:01) howSum tabulation
⌨️ (04:07:21) bestSum tabulation
⌨️ (04:20:50) canConstruct tabulation
⌨️ (04:38:06) countConstruct tabulation
⌨️ (04:50:23) allConstruct tabulation
⌨️ (05:07:44) closing thoughts

⭐️ Special thanks to our Champion supporters! ⭐️
🏆 Loc Do
🏆 Joseph C
🏆 DeezMaster

Learn to code for free and get a developer job: https://www.freecodecamp.org

Read hundreds of articles on programming: https://freecodecamp.org/news

And subscribe for new videos on technology every day: https://youtube.com/subscription_center?add_user=freecodecamp

source

50 replies on “Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges”

3:21:33 how is that not index out of bound ? you make table[i+2] and table[i+1] and your i iterates to n, so if you have n=6 you trying to increase table[8] and table[7] when you only should have indexes from 0 to 6

Going through these in python. For canConstruct, I can't get the basic recursion to break. That is, it doesn't slow down like at all. I am using startswith() and lstrip(). Is it possible these are more efficient?

In the canSum function, adding a modulus check is a massive improvement cuz if target % i != 0 then i is not going to generate the target anyways + it is better to know the reminder..
10%3 = 1 then you can not generate 10 using 10 what do y'all think

You said in the grid traveler tree that swapping rows and colums would give the same result, but did you put that in your code?
Also, in the bestSum tabulation, won't any tupel that was first added to any index be the shortest since it reached the index first?

How can I solve the sumWays (and the problems that variate from it), if the question asked me to use each element of the array at most once, (e.i. suppose you have k coins, and an array of n elements that each element has it's value, and we might have 2 or more elements with the same value (price).
in how many ways can we spend the k coins?
I've seen this problem in a programming contest but couldn't solve it and couldn't find the solution anywhere since then.

Here's the c++ code of fibonacii algorithm
#include<bits/stdc++.h>

using namespace std;
int fiboNumOptzUty(int n , int r[]){

if(r[n] != -1)

return r[n];

else {

r[n] = fiboNumOptzUty(n – 1 , r) + fiboNumOptzUty(n – 2 , r);

return r[n];

}

}

int fiboNumOptz(int n){ // Using Dynamic Programming T.C –> O(n)

int r[n + 1] = {0 , 1 , 1};

for(int i = 3; i <= n ; i++)

r[i] = -1;

return fiboNumOptzUty(n , r);

}
int main(){

cout<<fiboNumOptz(20);

return 0;

}

Came here after watching lecture from MIT about DP, this video is super cool and it is inspiring to code DP problems. MIT's lecture was made by chalk on black board, boring and confusing. Man, you are better than MIT's professor !!!

Signed in to give my appreciation for all your hard work, and GREAT work, putting together this series. Easily the best teaching series on the subject I've seen. Only a few errors that are easily overlooked. Only issue I had was I was converting the problems into C++, but that's not a knock on the series, if anything, the fact that I was so easily able to convert your solutions to C++ is indicative of a thorough explanation of the problems rather than just coding examples.

Thanks! I wish you did more!

In Spanish Wikipedia there is a pseudocode about Fibonacci numbers with O(log2(n)) order, it's based with mathematical demonstrations, without recursion or adding an artificial object. The only feature is maths. Here is a java code i've made, it's very easy to write it in other language:
public static int fibonacci(int n) {
int a, b, c, d, i, auxOne, auxTwo;

if (n <= 0) return 0;
i = n – 1;
auxOne = 0;
auxTwo = 1;
a = auxTwo;
b = auxOne;
c = auxOne;
d = auxTwo;
while (i > 0) {
if (i % 2 != 0) {
auxOne = d * b + c * a;
auxTwo = d * (b + a) + c * b;
a = auxOne;
b = auxTwo;
}
auxOne = c * c + d * d;
auxTwo = d * (2 * c + d);
c = auxOne;
d = auxTwo;
i /= 2;
}

return a + b;
}

I tried to implement the logic in Java/.. with numbers as ArrayList<Integer> and memo as HashMap<Integer, ArrayList<Integer>>… for BestSum(). the recursive logic is working fine but in memoized versions I am getting wrong value for last case.. it seems garbage ..something like [25, 1, 1, 2, 1, 2, 1, 2, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 12, 5, 1, 2, 5, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 5, 25, 1, 2, 2, 5, 25, 1, 2,25]… In JS the same logic works…
At the end of my wits about this..

1:45:44 I think the time complexity mentioned here is not correct, since it's based on thinking that the array copying operation will happen for every recursive call, which is not true. That operation will only happen once an array object has been returned, and since the only time you return an array object is when you've found a possible path, then you know every recursive call from that point onwards will be part of the early return, meaning it will return, at most, m times.
Since the array copy operation is O(m) and it is done m times, this means that the additional running time cost of it would be O(m^2). If you plug that in the time complexity of the whole algorithm, you'll get O(n^m + m^2). You could leave it like that and argue that, for some values of m and n, the m^2 term will be higher than the n^m, but I'd simply drop the m^2, since those cases only happen for a few values, and it further simplifies the running time.

Thus, I think the correct running time should simply be O(n^m)

does const make memo accessible for every fib call that has no memo argument? i mean as far as I can see, memo is being created every fib call that has no memo and this wont work too well if I want the Fibonacci number 50, I tried to call fib.memo and its undefined, at the end I did it with a global array instead of an object.

Before starting this video, I am going to take a vow to complete this video by this week, Because many times I started watching a tutorial and left it in the half — in the busy schedule at the university I was never able to complete any video that is longer than 3 hrs, But now in the sankranthi holidays I want to complete this video entirely…

1:21:00 – There is a quick way to get a false answer nearly immediately. Look at the gcd of all numbers less than the target. If that gcd is not a divisor of your target, then the answer is false. I suspect there may be a way to use algebra to come up with a fast answer to this problem that doesn't involve recursion or dynamic programming.

For fib tabulation, other languages than JS would not be happy if you're trying to edit the indices that are out of bounds, would a fix involve just a check if it's still within the array?

Leave a Reply

Your email address will not be published. Required fields are marked *