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

Learn how to use Dynamic Programming with Java 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 Structy. Structy is a website for learning data structures and algorithms for technical interviews. Learn data structures and algorithms: structy.net/
Check out Alvin's channel: / alvintheprogrammer
⭐️ Contents ⭐️
(0:00:00) course introduction
(0:01:38) fib
🔗 structy.net/problems/fib
(0:34:02) tribonacci
🔗 structy.net/problems/tribonacci
(0:47:05) sum possible
🔗 structy.net/problems/sum-poss...
(1:04:18) min change
🔗 structy.net/problems/min-change
(1:22:22) count paths
🔗 structy.net/problems/count-paths
(1:39:02) max path sum
🔗 structy.net/problems/max-path...
(1:52:56) non adjacent sum
🔗 structy.net/problems/non-adja...
(2:08:22) summing squares
🔗 structy.net/problems/summing-...
(2:21:50) counting change
🔗 structy.net/problems/counting...
🎉 Thanks to our Champion and Sponsor supporters:
👾 davthecoder
👾 jedi-or-sith
👾 南宮千影
👾 Agustín Kussrow
👾 Nattira Maneerat
👾 Heather Wcislo
👾 Serhiy Kalinets
👾 Justin Hual
👾 Otis Morgan
👾 Oscar Rahnama
--
Learn to code for free and get a developer job: www.freecodecamp.org
Read hundreds of articles on programming: freecodecamp.org/news

[@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

[@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

[@MyCodingDiarie]

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

[@justindouglas3659]

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

[@arnavsharma2094]

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

[@Yash42189]

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

[@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!

[@carloseduard317]

Amazing lesson Teacher! Than'k!

[@CodingAlways]

I love your lectures... ❤️🥰

[@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

[@jishnuanchery]

this is really good. Thank you!

[@amalayounes]

This is amazing stuff!! Thank you so much.

[@thusith-tec307]

Wow... Java. Thank you

[@sammetanagasrinivas5542]

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

[@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?

[@techwithdipufrom0ton621]

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

[@minhtriettruong9217]

Alvin lets goooo!!!

[@theencryptedpartition4633]

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

[@ankitg6454]

Many many thanks

[@icarus7247]

Thanks

[@anon-fz2bo]

hell yea i love dynamic programming

[@chovuse]

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

[@davidchang3252]

Thanks!

[@johncysamuel]

Thanks👍❤🙏

[@user-pj7ub4ir3u]

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

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

[@kwaleyelamusilizoikafa6197]

More Java content please

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

[@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.)

[@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?

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

[@user-cd3ul1ns2q]

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

[@ForRo3sS]

This is good

[@faroukzouaimia2494]

Is there one in c++

[@-karter-4556]

Finallyyyy!!!!

[@vidhikaushik738]

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

[@fumano2679]

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

[@fieryscorpion]

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

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

[@soumadip_skyy_banerjee]

👌🏻

[@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

[@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

[@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?

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

[@tahitivn]

view on many videos, this is easier to understand concepts

[@rithiksingh4352]

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

[@ovskihouse5278]

I wish do it with JS or Python

[@alexjohnson6192]

the concepts are way more important than the language implementation

[@MarouanBoukli]

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

[@Daydream_Dynamo]

Next up with Python, !!

[@rebelgirl3107]

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

[@wilfredomartel7781]

❤

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

[@_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

[@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;

[@forheuristiclifeksh7836]

3:23

[@CodingAlways]

Hiii

[@Sisyphus3.14]

tutorial hell

[@yo_soy_Kriti]

good for beginners bad for intermediate 😂😂

[@killeredits4400]

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

[@user-yv7gx8gm3f]

Is this for beginner ?

[@lovely-shrubbery8578]

No, its an upper intermediate computer science topic.

[@amaanullah13]

No

[@Max-tq1ig]

Your mustache is gone, Alvin!

[@neilclay5835]

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

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

[@Travelophile]

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

[@CodingAlways]

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

[@souvikghosh5768]

Kolkata?

[@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!

[@TVSh0rts]

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

[@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

[@conphident4]

Thanks!

[@sadiulhakim7814]

Thanks

[@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;