Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

For tabular bestSum, you don't have to compare the length of the arrays. If you're iterating through and filling in the future values as you go, you can just skip if the value you're filling isn't null.

Thanks!

Just completed this 5hrs instruction, so helpful and so thankful!!!! My friday night gone

So far the best video I have gone through for DP!!!, Thanks Alvin for taking the time for such quality content 😊😊

Why was the time for cansum() still O(m) after we had the memo object

How does the gridTraveler memoization account for the case where we have the same arguments but flipped order? i.e gridTraveler(a,b) and gridTraveler(b,a). Wouldn't the flipped key not be detected in the memo object?

Hard to understand for beginners. İt pure perfect.

Never seen such a good clear explanation of how to calculate time complexity. Which way would you prefer to get the nth element in a Fibonacci sequence? recursive way or in a for loop?

one of the best explanation videos i've seen covering dynamic programming topic

I’m new to programming, Can someone help me please ?

I have tried to follow this video but the moment I run the cmd of “ Node fib.js “. I get the error message:

“ The term node is not recognized as the name if a cmdlet ”

I don’t know how to setup the environment on VS to follow this video. Can you make a video of how to setup environment for this video ? Or someone in the comment help ? :) Thanks

F

Recursive programs are in use here and there, but I was a software engineer from 1975 to 2005 working for Pratt & Whitney Aircraft, a Route 128 CAD/CAM company, Apollo Computer (Sun Micro competitor), and Knight Securities (Nasdaq Market Maker start up). In all that time, I never wrote any recursive code, or changed any recursive code. When I retired i wrote a Scrabble playing program, to see what recursive programming was like.

One of the worst unclear courses I’ve ever seen. Can’t understand all of the positive people in the comments.

a better way of fibonacci function is the next one (it is in Scala, but its the same for any language):
def fibonacci(n: Int): Long = {
@tailrec
def faux(n: Int, fa: Long, faa: Long): Long = {

if (n == 0) 0
else if (n == 1) 1
else if (n == 2) fa + faa
else faux(n - 1, fa + faa, fa)
}
faux(n, 1, 0)
}

Amazing explanations. Question regarding gridTraveler. We understand that gridTraveler(2,1) and gridTraveler(1,2) produce the same result, however, Alvin's implementation does not take that into consideration, right? Wouldn't we want to check the memo for a key of 'm,n' as well as a key of 'n,m', and if neither are in there, set both? ie, memo['m,n'] = memo['n,m'] = gridTraveler(m-1, n, memo) + gridTraveler(m, n-1, memo), no? I may be overthinking but looking for any insight

I think case where any number is equal to 1 should be considered as a base in case of gridTraveler memoization. We dont need to go to zero. What is your opinion ? Please reply.
Thanks for this beautiful course. 👍

ShortestSum can be done simply by sorting the input array in reverse order then shove it to the earlier function which returns list of numbers that add up to target sum. Don't understand why we choose to go this way. Someone please explain.

Amazing, didn't know how to efficiently solve fibonacci, didn't really know what time and space complexity was, never heard of dynamic programming yet I understood this super easily (I know the first problem is bar far the easiest)

For the canSum shouldn't be the key "k+array"? Because if we only use the k it might return an error if there are duplicated k values

Thanks, very good macro tutorial

Hello Alvin, this is an Amazing content.
A question on canSum, if have a target value as an even number and then one of my items in the list is 2, it will always return true. Eg, 6, [2,3,5])

I have an issue with python best_sum problem. My code:
def best_sum(target_sum, numbers, memo = {}):
if(target_sum<0):
return None
elif target_sum == 0:
return []
elif target_sum in memo:
return memo[target_sum]
else:
shortest_res = None
for num in numbers:
res = best_sum(target_sum - num, numbers, memo)
if res is not None:
res.append(num)
if shortest_res is None or len(res) < len(shortest_res):
shortest_res = res
memo[target_sum] = shortest_res
return memo[target_sum]
Can anyone help and point out the problem?

Thank you Alvin. This was a great course!

"Enter a potent pot" he predicted Alexander in elden ring

I almost died but this helped me a lot, thanks.

The canSum problem had me thinking for a bit but why use a recursive function using a base - num? When you use a modules calculation you can run through it like nobodies business in a single run!

(runtime 3.18ms in powershell with base 180000 and numbers array (500,5,100))
function new-canSum{
param([int]$base, [array]$numbers)

foreach ($num in ($numbers | Sort-Object -Descending)){
$base = $base % $num
}

if ($base -eq 0){return $true}

return $false

}

If you really, _realy_, want to you can still use a recursive function (but at 3.24ms it's waaaayy slower 😂):
function new-canSum{
param([int]$base, [array]$numbers)

if ($base -eq 0){return $true}

foreach ($num in ($numbers | Sort-Object -Descending)){
return new-cansum -base ($base % $num) -numbers $numbers
}
return $false

}

For the canSum problem once it returns true won't the previous calls all just return true and finish execution? why do we maintain it, we can just maintain a hashset and if a number is in hashset it means it returns false. Here is the code for reference-
public static boolean canMemoSum(int[] numbers, int targetSum, int pos, Set<Integer> memo) {
if (targetSum == 0) {
return true;
} else if (targetSum < 0) {
return false;
}
else if (memo.contains(targetSum)) {
return false;
} else {
for (int i = pos; i < numbers.length; ++i) {
if (canMemoSum(numbers, targetSum - numbers[i], i, memo)) {
return true;
}
}
}
memo.add(targetSum);
return false;
}

In the howSum... Is it really necessary to spread the remainerResult. why not just push the value and return the array itself?

Who needs stupid university professors when you got a legend like Alvin explaining DP. Very good explanation!!

in the grid traveler problem you can actually take a base case of n==1 || m==1 because if eathier on them is equal to 1 there would be only one way to travel all the way right or all the way down and it reduces the time complixity like i wasn't able to compute GT(18,18) in the video method but after i changed the condition i was able to do that after a few seconds

"cool..."

Overall great tutorial, appreciate it! I was bit lost when it came to defining the time-complexity of canSum, not sure if the tutor was going too fast. But great effort! 👍

I cannot believe that this quality of teaching material is for free!! Your are amazing!!

I'm here after watching graph algo. I am a data engineer and I always struggled to understand the space and time complexity, this animation is all I ever wanted. This is by far the best video I watched on dynamic programming. Moreover, Alvin has that charm to keep me captivated for long hours without loosing focus. Keep up the great work man!

Can't believe this tutorial is free! Thanks Alvin, you are a great teacher!!!

I just don't know what magic you did with this video, it just completely changed the way i thought solutions and now I am able to do medium level problems like a cake walk. Can't thank you enough❤

For grid traveler, you can make another minor optimization by modifying the base cases as such -

if (m == 0 || n == 0) return 0;
if (m == 1 || n == 1) return 1;

Instead of using AND, use OR when returning 1

Because if you have a (1, m) grid or a (n, 1) grid, there is always going to be only one way to travel through it and when you do an OR statement, then it would simply return at the 1xm state instead of decrementing the m or n until you reach 1x1 to satisfy the AND condition.

It is also important to call the m == 0 or n == 0 condition before doing this to ensure that a 1x0 or 0x1 grid returns 0 and not 1

very clear and concise explanation of dynamic programming! definitely enjoyed learning it all the way to the end. hope there's more tutorials like this to come.

I am 45 mins in, but I had to stop to drop this comment. This is hands down one of the best tutorials I've ever seen.
Alvin is a true teacher. I am blown away by his style. I have taken paid courses on this topic, but this is the first time I am understanding what this is about. I can't wait to finish this tutorial.
I am going to go for all your courses.

Could someone explain me why m == 1 or n == 1 is not a base case, like if one of the coordinates will be 1 then its obivous that there is only one way to go to the end of the grid?

for bestSum memoization. wouldn't it be easier to just get all the possible ways and then do a check for the minimum once?
rather than at every node of the recursive tree?

like get all possibilities and just do a minimum after getting all the possibilities.

Great course! Thanks.
Follow up question, for fib tabulation, your array size is n+1, you execute the for-loop till i <= n, say i = n, you will do table[i+1] and table[i+2], which is when you will end up writing to the array index beyond the allocated bounds for i+2, is that correct?