# Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges

July 21, 2024 2024-07-21 18:25## 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

source

## Comments (34)

## @JamesBurchell69

Outstanding course. Thank you so much

## @sanjaybhosale8296

For bestSum can we do BFS instead of DFS as it will find shorter sequence faster, also we can sort the array in reverse order if using DFS

## @enriquegrageda

Finally, the teacher we all needed. Great job man!😀

## @CodeMaster-w5g

This is a great course i recommend to watch

## @yassinuzu2351

appreciate the wonderful work , but if you made it in c++ , it would much better

## @user-nw9ch3zi9d

On 1:45:57, there should be n**m + m instead of n**m * m because the array is null if I dont have an answer and that is at max O(1) time, but If in any recursive call I have an answer, it reutrns and returns over not going to the next recursive call, so it should be m**2+ n**m.

On 1:49:25, the time complexity should be O(n*m + m**2) instead of O (n*m**2)

## @sahilshah727

You are such a good teacher, thank you for posting this

## @Dr.Logistik

I just noticed. 33:27 is the same were of how morse code is done…start with E at the top, a short dit goes left a long dah goes right…rinse and repeat to get to letters you need….huh interesting

## @kirillzlobin7135

1:04:09 Isn't space complexity in memoized version m*n?

The memo object stores results for each of the m⋅n unique subproblems.

Is my logic correct?

## @osamaxz5720

thanks for this explanation bro ✨

in the problem "howSum" for real I don't like return an array even if the language accept it by reference (in js the array is a special object as you know) and python is the same when you send any collection to a function it will accept by reference so is there another way without returning an array ?

I found this way using the stack so in each call if you didn't found an answer yet then add the number in the stack but when I finish the branch ? if you got no result then pop from the stack

the stack should be in the global scope but in python I used a nested function to make the function pure (without side effect)

another thing about my solution that's I solved the problem without watch you how you solved so I started from zero then add the number from the array to the sum and then recursive start

so in my code if you asked for 0 it will return true (specially in the canSum problem) so I checked if the target is zero and the array contains 0 I will return array of one element (zero) (this will go with O(n) as time complexity) without further talking.

Here is my memo solution for canSum in python:

def howSumDP(target, numbers):

memo = dict()

# Save the indices for numbers you got them, this will take a space O(m)

stack = []

# Indicating whether we found an answer or not

weFoundAnswer = False

def add(sumy):

nonlocal target

nonlocal numbers

nonlocal weFoundAnswer

nonlocal stack

# Base Case One: if we already has an answer

if weFoundAnswer:

return

# Base Case Two: if the sumy exceed the target

if sumy > target:

return

# Base Case Three: if the summy is equal to the target

if target == sumy:

weFoundAnswer = True # Save that we got an answer

return

if sumy in memo:

return

for i in range(len(numbers)):

memo[sumy] = 1

if not weFoundAnswer:

stack.append(numbers[i])

add(sumy + numbers[i])

if not weFoundAnswer:

stack.pop(-1)

return

# Maybe the user enter 0 and numbers doesn't contain zero then ?

if target == 0:

if 0 in numbers:

for num in numbers:

if num == 0:

return [0]

return None

# Normall way

add(0)

if len(stack) == 0:

return None

return stack

## @softvibes1602

In the grid traveller problem, since there are m – 1 downward movements and n – 1 rightside movements, and the number of downward movements and right way movements remains constant with only the order of the movements that change, we can find out the answer using a mathematical formula using the conepts of permutations and combinations. since we are arranging the order of m – 1 + n – 1 movements, the total possibilities will be (m + n – 2)! and since two downward movements and two right way movements are the same and there is a repetition of the same downward or right way movement, we need to divide it by (m – 1)! and (n – 1)!. so the answer to the problem is simply (m + n – 2)!/((m – 1)!*(n – 1)!)

## @badrinathpetla

how in earth O(2^(n/2)) same as O(2^n) , just take the value of n = 20, its difference of 10^3 and 10^7

## @srikanths5464

In the grid traveller problem, we can make the first condition m== 1 or n==1 . Since the problem is symmetric in m and n, we can ensure that m >= n while adding to the map and searching in the map. This problem is actually calculating (m+n )Choose m. While solving fibonacci using tabulation, we can optimize to get O(1) space and for grid traveller we can get O(n) space complexity.

## @user-uy7lv4rb2l

I watched it before like till 2:12:00 I am like super confident 'Yeah you got this DP'. Now after a while I hit this question Coin Change…. And really I have no clue how to do it.😂🤭

## @kapilgyanchandani

Very Nice Course, loved it.

Just one thing in canConstruct Tabulation solution,

if(target. slice(i, i + word.length) === word) {

table[i + word. length] =true;

}

We can check if(i + word.length <= target.length), considering the fact that there can be a word with very large length, unnecessarily increasing the table size.

## @helloitsme7553

One correction: 2^n and 2^(n/2) are not the same complexity.

To be of the same complexity in this case, means that there exist positive constants A,B s.t. A*2^n <= 2^(n/2) <= B*2^n

## @spandansaha5663

at 1:27:41 line no. 10 shouldnt it be memo[remainder] instead of memo[targetSum] as through the if statement we have confirmed that it returns true for remainder and not for targetSum, so wouldnt that lead to discrepancy,

i ran my code with memo[remainder] and it also works just as fast so i am not sure what is the correct code here

can anyone help pls

## @PPunyacharan

Fantastic video @freeCodeCamp. I identified a small mistake at 46:58 in the tree diagram: the rightmost leaf node should be (2,0) and not (0,0) or am I missing something?

## @DlExNjnjaOP

incredible course but small mistake at 47:45 last bottom right node should be 2,0

## @natnaelsisay1424

I can only say .. Thank you. If you want to learn DP, i don't know if there is a better video than this

## @rojinapanta6224

One little confusion in the grid world problem where do you check [m, n] or [ n, m ] are same thing ?

## @user-uh2wj5oc4i

1:52:00

## @sarveshkhandelwal6039

If I do this in python, would the memo passed into the function be copied every time in turn creating different copies of memo with every function call?

Great course btw! Definitely the best I've come across and I wish I watched it sooner!

## @karimjunior-wo7zq

He made it looo so simple ❤

## @eswarv5813

Thank you so much ❤❤

## @eswarv5813

Thank you so much ❤❤

## @g0nt411

3:25 I have encountered the same problem in python when creating a 2d array with [[0]*row]*col.

## @colonelsanders2038

For canConstruct, what about the indexOf call for time complexity? It seems like it has to search through the target linearly for the word, adding another m. Also, I think it'd be fast to use startsWith because it's constant time.

## @LinhNguyen-ym8yg

Just a quick note for the Tabulation on the fib. JS actually access the out of index element in the array and read it as undefined. I suppose it also ignores the addition between an integer and an undefined object? I'm following along and translating the code to Python so it's just something I noticed and want to make a note.

## @lesteI

This video was awesome! I learned a ton from it. I really appreciate the time and effort you put into making this video. I can't thank you enough.

## @kowpen

This is an excellent lecture. Really liked how he unwrapped the concept to the core and presented so it is easy to understand. The visuals were of huge help to grok the topic. Great work!

## @The_Pariah

I love the "Over 1 million views" sticker on the thumbnail when the video now has x4 that amount.

There's some good stuff in this vid.

## @sehajsingla3029

Hands down. I am not a very good student of programming however, the way this person teaches is impeccable. I am solving questions side by side and I am getting all the answers right within the first go. Thank you so much for your efforts and you should really teach me everything because I am UNSTOPPABLEEE.

## @whatif7810

console.log(canSum(13,[2,5])); // true with memo how?