Пікірлер
@SaiDharahasReddyIndrakanti 3 күн бұрын
are we using bottom to top approach here?
@goshapoopkin 7 күн бұрын
Everybody: DP is so hard to explain to begginers- Andrey Grehov: Hold my beer *proceeds to explain DP in the most simple way possible*
@goshapoopkin 7 күн бұрын
thank you for doing this, it is really appreciated. can i just ask what language did you use to write the code?
@andreygrehov 7 күн бұрын
Thank you. The code is in Go Programming Language.
@edwardduong6914 27 күн бұрын
Somehow you look like Victor Perkins to me.
@andreygrehov 23 күн бұрын
lol
@nhatho1723 29 күн бұрын
You can’t fool me, this is just Fibonacci lol
@shaurya478 Ай бұрын
It is the best it can gets. Thanks Andrey.
@codeduel Ай бұрын
If order does not matter, Here is the correct version: public static int makeChange(int n, int[] coins) { int[] dp = new int[n + 1]; dp[0] = 1; for (int coin : coins) { for (int i = 1; i <= n; i++) { if (i - coin >= 0) dp[i] += dp[i - coin]; } } return dp[n]; } This gives combinations instead of Permutations (where order matters)
@shaurya478 Ай бұрын
Here is the code for example (Java): static int minCostStairOptimized(int n, int k, int[] cost) { int[] dp = new int[k] dp[0] = 0; for (int i = 1; i <= n; i++) { int min = Integer.MAX_VALUE; for (int j = 1; j <= k; j++) { if (i - j < 0) break; min = Math.min(min, dp[(i - j) % k]); } dp[i % k] = cost[i - 1] + min; } return dp[n % k]; }
@muhamadaminibragimov5096 Ай бұрын
Thank you
@muhamadaminibragimov5096 Ай бұрын
Thank you very much
@myrachoantonio8832 2 ай бұрын
This amazing thank you so much for the tutorials bi
@denver-reed 2 ай бұрын
4 years later from your initial upload and this is still helping me greatly. Thank you, Andrey!
@Wuaners 2 ай бұрын
I did't get the idea. Am I stupid? 😓😰
@rafaelortega1376 2 ай бұрын
In the k version of the problem, you define only two initial cases. However it should be three for one of the test cases. Right?
@ethernet764 3 ай бұрын
1 being even and 0 being odd is ... odd 😅
@cobaroja3529 3 ай бұрын
i have a question, i think that all the information we need is in list from, why we write another loop?
@ethernet764 3 ай бұрын
Here is my attempt for space complexity O(k): int paid_staircase(int n, int k, const int *costs) { int *dp = alloca(k * sizeof(paid_staircase(n, k, costs))); // NOTE: 0 is the 1st stair for (int i = 0; i < k; ++i) { dp[i] = costs[i]; } for (int i = k; i < n; ++i) { int min = INT_MAX; for (int j = 0; j < k; ++j) { min = min < dp[(i - (j + 1)) % k] ? min : dp[(i - (j + 1)) % k]; } dp[i % k] = costs[i] + min; } return dp[(n - 1) % k]; }
@ethernet764 3 ай бұрын
Another variation could be: you're only allowed to take either 1 step or 3 steps. How could that be implemented?
@ethernet764 3 ай бұрын
Code in C if anyone wants: int nSum(int n) { int *dp= alloca(1 + (n * sizeof(nSum(n)))); dp[0] = 0; for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1] + i; } return dp[n]; }
@anniehu4929 3 ай бұрын
The new intro is so cool!
@alexc7289 3 ай бұрын
the constant 'c' has to be greater than 1 for "exponential" time to make sense.
@024_habeeb7 3 ай бұрын
Please teach advanced dp and other topics as well, man these lectures are too good
@theremin1441 3 ай бұрын
linear runtime: def sum(n): return (n+1)*(n/2)
@BnABoAbdAllah 3 ай бұрын
your children are so kind
@abhivaidya2619 3 ай бұрын
You are amazing....
@gengi-po3cx 4 ай бұрын
Great series so far, my c++ solution: #include <bits/stdc++.h> using namespace std; int main() { while(1) { int n,k,i,minim,j; scanf("%d%d",&n,&k); vector <int> cost(n+1); for(i=0;i<n;i++) { cin >> cost[i]; } vector <int> dp(k); for(i=0;i<k;i++) { dp[i]=cost[i]; // printf("%d ",dp[i]); } for(i=k;i<n;i++) { minim=INT_MAX; for(j=0;j<k;j++) { minim=min(minim,dp[j]); // printf("skibidi");3 } dp[i%k]=cost[i]+minim; // printf("%d ",dp[i%k]); } printf("%d ",dp[(n-1)%k]); } }
@luzengyuan5326 4 ай бұрын
This is the greatest video which makes me understood dp. Thanks
@praveenkumarsadhasivam 4 ай бұрын
I think, drawing the recursion tree first and then deriving the F(n) based on the recursion tree helps in easier understanding of this problem.
@maheshj01 4 ай бұрын
It blew my mind when I was able to solve leetcode 746 after watching this video. Keep Making great content 🔥
@maheshj01 4 ай бұрын
Anyone looking for solution to leetcode 746 solution ``` class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # f(i): cost to reach at step i # f(0) => 0 # f(1) => 0 # Since we can start at either 0 or 1 # Bottom up Approach costs = [0, 0] for step in range(2, len(cost)+1): # [10, 15, 20, 24, 15] goal -> 5 = 39 # f(0) -> 0 -> 1, 2 # f(1) -> 0 -> 2 , 3 # f(2) -> min(cost[0] + f(0), cost[1] + f(1)) => 10, 15 => 10 # f(3) -> min(cost[1] + f(1), cost[2] + f(2)) -> (15 + 0, 10 + 10) => 15 # f(4) -> min(cost[3] + f(3), cost[2] + f(2)) -> (24 + 15, 20 + 10) => 30 # f(5) -> min(cost[4] + f(4), cost[3] + f(3)) -> (15 + 30, 24 + 15) => 39 cost_step = min(cost[step-2] + costs[0],cost[step-1] + costs[1]) costs[0] = costs[1] costs[1] = cost_step return costs[1] ```
@maheshj01 4 ай бұрын
You make dynamic programming look so simple, thanks for this great video.
@TheKirk1989 Ай бұрын
looks like challenge #try_to_solve_lc_hard_dp ;D
@soumyajitganguly2593 4 ай бұрын
this can be done using DP even without the top-sort
@miri9131 5 ай бұрын
thank you !!
@aabhajyoti1011 5 ай бұрын
Hey @andreygrehov, I have a question. For the base case in the stair case for F(0), we took F(0) as 1, can you help me understand why? Since F(0) is going to be the ground level and we are not taking any step to get there; then why do we take it as 1 and not 0?
@Enzoerb 5 ай бұрын
Thank you so much for this series!! What a great course (I will probably rewatch the coin change classes, btw)
@swapnilyadav4490 5 ай бұрын
fucking legend
@rahmanjahdasa212 5 ай бұрын
Well done, I learned a lot, thanks, I hope you continue making other ones
@AllenRodger22 5 ай бұрын
nice
@peepeechowmein-vh5uy 5 ай бұрын
very good
@Enzoerb 5 ай бұрын
Now it is starting to get harder lol, I had to watch this one twice
@Enzoerb 5 ай бұрын
We can also do this same problem starting from the back, right? Because then the value on each dp would be the ways in which this point can lead you to the end Then dp[m-1][n-1] = 1, because there is only 1 way to get to the end from the end Then we would tun the for i = m-1; i <= 0; i- (the same for n) Adjust the conditionals so we don’t check after m-1 and n-1 (instead of 0) And update the rows to be checked to dp[i+1][j] and dp[i][j+1]
@Enzoerb 5 ай бұрын
What an amazing course!!
@chap_eau 5 ай бұрын
I will never thank you enough. great video and great playlist🎉🎉
@chap_eau 5 ай бұрын
THANKS a lot for this🫱🏻🫲🏼🫱🏻🫲🏼
@esmailkhorchaniarts1142 5 ай бұрын
huge thanks sir
@vivek.tiwary 6 ай бұрын
Objective function F(i) => # ways to reach to ith stairs
@manibhushankumarsingh5196 6 ай бұрын
00:05 Introduction to Optimization Problem in Dynamic Programming 00:54 Understanding optimization problems and applying dynamic programming 02:09 Dynamic Programming requires defining objective function and base cases. 03:17 Discussing the optimization problem approach in dynamic programming. 04:21 Dynamic programming solves optimization problems by finding the cheapest amount to pay. 05:34 Using bottom-up approach for dynamic programming 06:42 Dynamic Programming for Beginners 08:20 Time and space complexity analysis of the algorithm.
@scandio33 6 ай бұрын
does anyone know if F(i-10,1) is correct or not. It seems that if you have an odd amount of coins then take away an even number, you['d be left with an odd amount of coins. Hope someone can help me with that. great videos btw just left a little confused on that one
@nscini 6 ай бұрын
Thank you Andrey. Your series is well done. Both your english and your way to explain is very clear than very effective.
@maryamtaha3904 6 ай бұрын
Thanks alot for this series, but why are there no new videos
@newoob8902 6 ай бұрын
Thank you LEGEND! I hope you are doing well. This series still going strong after 3 years.