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”

can anyone give me code of howSum problem in c++?

Great video.

just wanted to ask. wouldn't @53:13 height of the tree will be (n + m) -1 .

Very well explained, easy to follow and understand. I would like to know what IDE you were using?

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

3:45 how canSum of 6 is true here???

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?

Quick question at 2:33:07: shouldn't target.indexOf also contribute with m in the overall time complexity? The internal implementation of indexOf is also O(m), just like target.slice

This tutorial is awesome with decent voice.

I really can not believe this is free content.

This is gold

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

Simply put: the best instructor ever. Congratulations Alvin! Your material is just pure gold!!!!

Thank you so much for this ! The best worthwhile 5 hours of my life ! 🙂

The teaching style is great, Alvin provides insights and a methodology for solving practical coding problems..

I knew memoization seemed really familiar. I had just seen a video about @cache in python a couple days ago.

This is so helpful, thank you very much!!

Great material!

I wonder how broad is the application of the tabulation approach. Can it always be an alternative to a recursive approach?

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 a teacher you are!!! Thanks a lot

In the cansum problem can't we just return true if 1 is present in the array? as any target could be achieved if 1 is there in the array

For pythoneers :

x=[1,2,3]

[*x,5] returns [1,2,3,5]

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!

this guy is a genius

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;

}

great video, love it!

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..

Alvin you're the goat!!!

This is awesome

For gridTraveller with memoization, shouldn't the space complexity be O(m*n) because our memo hash map will contain each cache for each cell of the grid?

At 48

47:00, the most right node of the 3rd level should be (2,0).

Does javascript automatically handle index out of bound errors?

In the tabulation example @3:21:38 when i == n, wouldn't i+2 be out of bound?

Thanks!

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.

Why do we measure time complexity by counting number of nodes at leaf level and not the total number of nodes in the tree since our recursive function has to travel to all the nodes?

thanx, you help me in understanding other big problems, I was scratching my head off.

Спасибо!

This man is the real deal. Protect him. Awesome course on DP

QUESTION for this (https://youtu.be/oBt53YbR9Kk?t=11376) time space complexiy for allConstruct problem: can't figure out why memoized version has the same time complexity as without memoization. i thought that memoization has to reduce time complexity, because we skip parts of tree during traversal.

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.

Huge memory overhead. Just don't use recursion. Use straightforward calculation for fib.

Very good course

Simply Beautiful

Thanks!

This is literally the best coding video tutorial I have ever seen. So slow, so methodical, so detailed. Thank you so, so much!

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?