Dynamic Programming with Java - Learn to Solve Algorithmic Problems & Coding Challenges

[@aanchaallllllll]

0:00: 💡 Dynamic programming is a method for solving complex problems by breaking them down into simpler overlapping subproblems and storing solutions to avoid redundant computations. 10:37: 🌳 The complexity of the recursive solution is very large and difficult to analyze due to the asymmetry of the tree. 21:27: 📝 The process involves calculating Fibonacci numbers and storing them in a memo to avoid redundant calculations. 32:21: ⏰ By implementing memoization, the time complexity of the solution improves to O(n). 43:20: ⏱ The code is too slow and needs memoization to improve its speed. 53:19: 📊 Implementing memoization strategy in a recursive algorithm can reduce the exponential complexity to linear complexity. 1:03:37: 💰 The goal is to find the minimum number of coins required to reach a target amount. 1:13:54: 🔑 The approach is to optimize for the number of coins needed to create a given amount. 1:24:17: 🌳 The problem can be represented as a tree, where each node represents a possible path in the grid. 1:34:31: 🔢 The code is implementing a recursive function to count the number of paths to a goal position. 1:45:46: 🔍 The code sets up a method to track a position in a grid and checks for base cases. 1:56:26: 🌳 The problem at hand involves a dynamic programming approach to finding duplicate subtrees in a larger tree. 2:06:57: 🔑 The code snippet describes the implementation of memoization in a recursive method using a hashmap. 2:17:21: 🔍 The code is finding the minimal sum of squares using a recursive helper method. 2:28:23: 🔢 The Java walkthrough for the counting change problem involves implementing a recursive method with an additional argument. Recap by Tammy AI

[@Legacyposh]

Thanks so much

[@rs4267]

Thank you for this video! I really appreciated the explanation of memoization using HashMap. However, I took a slightly different approach in my own code for calculating Tribonacci. Instead of passing the HashMap as a parameter in each function call, I decided to use an instance variable in my classe Source to store the memoized results. This makes the code cleaner and allows easier access to the stored values without having to pass them around. => public class Fibonacci { Map memo = new HashMap(); public static void main(String[] args) { Fibonacci fibonacci = new Fibonacci(); fibonacci.memo.put(0,0); fibonacci.memo.put(1,1); public Integer run(int n) { if (this.memo.containsKey(n)) { return this.memo.get(n); } // calculation and memoization... }

[@sidharth-singh]

I struggled with Dynamic Programming for past 3 years. This video is amazing! By the half of it, I was already on my way solving them. I like the last one. It was a different variety in itself. I thought of a solution actually storing the paths in a "Set" and then count the length of the "Set". I never thought of this way for this problem . Even though choosing or not choosing is a common pattern in recursion. THNAK YOU SO MUCH!!

[@pleasantdayNwisdom]

bhai maene bhi itna acha dp course nhi dekha , striver etc were not teaching simple way , mera yeh feel aaya , i saw his approach for 2 problems and then own my own till the last one ,stuck ho gya hu , mae bhi set wala hi soch rha hu , but pta h kuch better way ho skta h , i want to do this last question on my own

[@zakariaelmoumnaoui4912]

Finally Java this time

[@gradientO]

It's concepts that are important, not the language

[@Ganesan4510]

Python onlyone

[@Carlos-kv6hx]

I agree but like 90% of content is web dev here

[@-karter-4556]

@@gradientO there is memoric value in applying concepts in an already familiar programming language.

[@Saiyan412]

Yup 👍🏻

[@dkdraipur]

The best ever tutorial make on DP. Using HashMap removes all the ambiguity around the DP. Kudos

[@arnavsharma2094]

I would like to say thank you to the instructor for providing this knowledge for free on this platform

[@lawalrasheed_]

This is absolutely elite, thanks for making this available to the community for free. Just to build on this for learners here, you probably want to explore an iterative solution to the "non-adjacent sum" since large array inputs will blow up your call stack in the recursive approach.

[@allanguwatudde7623]

You mean bottom-up?

[@Website_TV_1]

This is exactly what I've been looking for! Dynamic programming can be tricky, but solving algorithmic problems with Java makes it so much easier to grasp. Can't wait to dive into these coding challenges and improve my problem-solving skills. 💻🔥 Thanks for making complex concepts so accessible!

[@bcampera]

Man there are great vids out there but you're the only one that made me really understand this in a simple manner, I don't feel stupid any more. Thank you so much!

[@makov2299]

33:02 This algorithm works only up to fib(46) including. In Java, the int data type has a maximum value of 2,147,483,647 , so if you wanna make the algorithm efficient for every value of n, change the int keyword with long . because if you don't fib(47) will return -1323752223 instead of 2971215073.

[@justindouglas3659]

Finally something i can use to learn. Thank you so much.

[@aammssaamm]

This is what needs to be used for the frontend components. Then the communication between components and branches is a breeze. You can send any event with any data to any point and fully control the sequence of those threads at any time. Then components have to be the object of the same class and share the same methods of communication.

[@vedangarekar1390]

Can you explain using examples of where this is used in frontend ?

[@aammssaamm]

@@vedangarekar1390 All frontend components should be organized in one tree which becomes a bus for communication between them. The simplest example is the DOM itself, but components may be more complex that just a single HTML tag. HTML becomes a template only for a component. There should be a common class “component/widget/actor”, which all component objects of different types are created from. The best way to understand is the Actor Model by Carl Hewitt. You can google “actor model javascript” to see various examples.

[@MyCodingDiary]

You're doing an amazing job at explaining coding concepts. Keep up the great work!

[@RodrigoRocha1980]

### Resumo Neste conteúdo, Alvin Zablin ensina sobre programação dinâmica, com foco em resolver problemas de Fibonacci de forma recursiva com memoização. Ele começa explicando os conceitos básicos da programação dinâmica e o problema de Fibonacci. Em seguida, ele mostra como resolver o problema de Fibonacci de maneira recursiva, incluindo base cases para 0 e 1. Além disso, ele introduz a estratégia de memoização, onde os resultados são armazenados para evitar cálculos duplicados e melhora o desempenho. Alvin também discute a complexidade de tempo e espaço do algoritmo, destacando a eficiência da abordagem de memoização. ### Destaques - 📚 Programação dinâmica é usada para resolver problemas complexos quebrando-os em subproblemas sobrepostos e armazenando soluções para evitar cálculos redundantes. - 🧮 O problema de Fibonacci é um exemplo clássico usado para entender a programação dinâmica. - 🤖 Alvin Zablin ensina como resolver o problema de Fibonacci de forma recursiva, com base em base cases para 0 e 1. - 📊 A estratégia de memoização envolve armazenar resultados para evitar recalculos, melhorando o desempenho. - 🕰 A complexidade de tempo do algoritmo de Fibonacci com memoização é O(n), enquanto a complexidade de espaço é O(n), tornando-o eficiente.

[@sathishkumar-rc4se]

In the Sum Possible Challenge he has added the Memo Hashmap inside the If Condition (1:03:45), In general if the Condition is met then the it return the value as True and Loop ends whats the Point in adding the Memo HashMap inside that Condition!

[@Yash42189]

here is chatgpt's answer Yes, you're right. Once any branch returns true, the answer for the top-level problem has been found, and you can halt further exploration. Any subsequent or sibling branches don't need to be explored. The recursive call stack will unwind, and true will propagate all the way up, ultimately indicating that the target sum can be achieved with the given numbers. The value in memoizing the result (true or false) for a specific target is to handle situations where you're exploring other potential branches or paths before you find one that leads to a solution. Memoization can also be beneficial if you're solving different instances of the problem (e.g., checking for multiple different target values) during the program's execution. However, within the context of a single invocation and after finding a valid combination, you're right that the memoized values won't be accessed since you'd halt the process and return true. If you're focused on optimizing purely for the scenario where you halt immediately upon finding a solution, you can indeed skip memoizing the true result in the current context, since it won't be accessed again. The key is understanding the trade-offs and tailoring the approach to the specific requirements and constraints of the situation at hand.

[@itsSunnyy0]

exactly, the main idea is false memos can save a few recursive calls, if its true it just returns so no point in caching.

[@minhtriettruong9217]

Alvin lets goooo!!!

[@leomamaci376]

Finally Java, been waiting for it so long 🎉

[@mihu86]

In the "max path sum" problem using double is not necessarily a good idea. Although it would require an extremely large grid with large numbers to fail, theoretically it can fail due to number representation / precision issues, especially as a "rolling sum" is being calculated (well, to be honest, this would require a long in the "main method" instead of int - but one should still think about these potential issues, that is the important bit here). It would have been more straightforward to simply use Integer.MIN_VALUE (or in case of really big inputs, Long. MIN_VALUE) in the initialization. (The performance can be slightly better as well for a really big input.)

[@thusith-tec307]

Wow... Java. Thank you

[@Yash42189]

this is such a fascinating way of solving problems! I love it!

[@pleasantdayNwisdom]

Thankyou Alvin Sir , I did Sum possible problem on my own , saw many recommended playlist on dp , but ur way of explanation worked for me ! Happy ! thankyou code camp :) but one slight doubt , like for this question sum possible , suppose if zero digit is required for amount =0 , then what would have been the base case?

[@manipurihunabopa]

Great tutorial because everything taught here is easy or made easy to understand.

[@fumano2679]

Hey found here through advent of code 2023 day 12 part 2. Greetings :)

[@hend3gossate]

besides dynamic programming we can traverse answer tree like bfs instead of dfs

[@amalayounes]

This is amazing stuff!! Thank you so much.

[@carloseduard317]

Amazing lesson Teacher! Than'k!

[@CodingAlways]

I love your lectures... ❤️🥰

[@icarus7247]

Thanks

[@RaviKumar-v9b6m]

Non adjacent problem I think we can easily solve using For loop

[@StarContract]

I think you have an error in the solution for the non-adjacent-sum problem. for the following list: [1,3,5,12,8,5] the result should be 17; your code result is 20. correction: return Math.max( nums.get(i) + max(nums, i + 2), maxNonAdjacentSum(nums, i + 1) );

[@sammetanagasrinivas5542]

Thanks for the video, I really got an idea about DP

[@susantamandal2782]

I was going through the Non Adjacent Sum Tree structure and found some of the portions are getting missed. I was looking for any better explanation. 1:57:00

[@anon-fz2bo]

hell yea i love dynamic programming

[@theencryptedpartition4633]

YASSS. I was doing my research paper or project on it just this term

[@RakeshPulioffical]

can you please upload videos on power BI you're channel is best learning resource for us

[@jishnuanchery]

this is really good. Thank you!

[@jayjaayjaaay94]

I don't understand count paths problem, you use c== grid.get(0).size() which actually get the right top? 🤔 🤔 Shouldn't we check the right bottom of the grid? c==grid.get(grid.size() - 1).size() Please help me

[@yourpoookieboo]

Half way through, i get the sums clearly cus of the tree based visualisation for dp or recursion nice hack there, however the count paths sum could have been a bit more in depth , anyway kudos

[@chovuse]

Great tutorials ! Please make your syntax text larger. Many Thanks !!!

[@vidhikaushik738]

Oh my god I am struggling with these kinds of problems and you heard it 😂😂

[@jayjaayjaaay94]

I don't understand, in count path problems, why it check c== grid.get(0).size? Isn't checking right top? 🤔 Shouldn't we check the right bottom? Which is c== grid.get(grid.size - 1).size?

[@ankitg6454]

Many many thanks

[@ka1pana]

The 0 base case in the Sum possible problem, qualifies as "true" is not clear. Question was are there ways of using the numbers given to add up to the amount. If Amount 0, and numbers are 1, 2, 3 we cannot use any of the numbers to add to 0 (assuming all numbers are positive), so the answer is false right ?

[@ShubhangiDutta]

I think that its referring to case where the amount can be made without choosing any option for the list- so even if you have say 1, 2 and 3, you can always make 0 by never adding any of them, hence true. The same applies to the minChange problem.

[@fieryscorpion]

Can you please do this using C# as well? Show some love to C#. It’s such a nice language.

[@-karter-4556]

Finallyyyy!!!!

[@conphident4]

Thanks!

[@kwaleyelamusilizoikafa6197]

More Java content please

[@tahitivn]

view on many videos, this is easier to understand concepts

[@Sisyphus3.14]

tutorial hell

[@Robo_Mark-8]

good for beginners bad for intermediate 😂😂

[@raghavamorusupalli7557]

To demonstrate a solution to the min change problem the selected problem instance must be so typical that the application of greedy method fails on it.

[@ForRo3sS]

This is good

[@johncysamuel]

Thanks👍❤🙏

[@santhoshjoruka2036]

In the count paths problem how did you come up with this logic countPaths(r + 1, c, grid, memo) + countPaths(r, c + 1, grid, memo)? anyone who understands can help on this.

[@ovskihouse5271]

I wish do it with JS or Python

[@alexjohnson6192]

the concepts are way more important than the language implementation

[@Daydream_Dynamo]

Next up with Python, !!

[@soumadip_banerjee]

👌🏻

[@faroukzouaimia2494]

Is there one in c++

[@Max-tq1ig]

Your mustache is gone, Alvin!

[@MarouanBoukli]

1:18:00 doesn't the minCoins get overwritten every time?

[@SphereofTime]

3:23

[@rebelgirl3107]

Sir, I have a question about dynamic programming, how can I reach you?

[@wilfredomartel7781]

❤

[@_sf_editz1870]

Please make trees and graphs in java please

[@aammssaamm]

If you cannot follow even a simple example, you'd better look for a simpler career.

[@_sf_editz1870]

@@aammssaamm thank you

[@mdhossen7082]

Hello freeCodeCamp how are you I hope you all are well, One request please make an "Object-C" mobile app development crash course please, Thanks;

[@CodingAlways]

Hiii

[@neilclay5835]

Too many "rights". It's a common problem.

[@GhithEdlbi]

Is this for beginner ?

[@lovely-shrubbery8578]

No, its an upper intermediate computer science topic.

[@amaanullah13]

No

[@killeredits4400]

Hey hii.....I want complete begginer level to high DynamicProgramming DSA in python....

[@keineangabe8993]

The lecturer probably knows this, but i cant watch a video where somebody uses an explicit HashMap in a method signature. Makes me wonder which other bad principles are included that i might not notice.

[@jagi7976]

What do you suggest instead?

[@keineangabe8993]

@@jagi7976 always use interface types, so in this case Map. It doesnt matter if it does not make a difference in this specific case. Some things need to be like muscle memory.

[@Yash42189]

so you have nothing good to say about this great, free lecture? What principles dude, he isn't writing enterprise solutions. It is just a single method. You want him to use dependency injeciton too?

[@keineangabe8993]

@@Yash42189 Dependency injection would include unnecessary complexion. Using an interface would not, it barely changes what he would have to write. And no, i have nothing good to say because i did not watch it after that, as i already said.

[@tarundjremix2323]

Wait, do you think cryptocurrency will crash? I dont think so. More and more companies are integrating cryptocurrency into their operations: Amazon, Cannafarm Ltd, Burger King, even Starbucks, dude!

[@wildarmy1861]

I dont know, dudes. I think crypto and all these ICOs are just a bubble. Well, crypto is good for transfers and so on, but I dont engage in trading and staking either. Its too risky. My friend recently lost $5000 there. I invest crypto in real business

[@CodingAlways]

My name is bikram barman... From India West Bengal

[@souvikghosh5768]

Kolkata?

[@TVSh0rts]

Java is great language, but not for coding interviews come on...

[@Travelophile]

this will fail for input [1,2,5] , due to the memoization

[@muradmemmedov1055]

In your implementation(tribonacci), n(0) and n(1) both return 0, which is incorrect. n(1) should return 1 @alvinzablan

[@sadiulhakim7814]

Thanks

[@davidchang3252]

Thanks!

[@silentworldsound]

Hello freeCodeCamp how are you I hope you all are well, One request Please make an "Object-C" mobile app development crash course please, Thanks;