Minimum Operations to Reduce X to Zero | Dynamic Programming | Leetcode
HTML-код
- Опубликовано: 8 окт 2024
- This video explains a very important dynamic programming interview problem which is to find the minimum operations to reduce X to 0.This problem is typically based on making choice between 2 options.I have first explained the problem statement and then I have explained the intuition for solving this problem. I have first explained the recursion approach and then I have explained the optimization using memoization top down dynamic programming approach.I have explained the CODE at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL LINKS:-
01 Knapsack Recursion: • 01 Knapsack using Recu...
Number of subsets with given difference: • Number of subsets with...
Rod Cutting Problem: • Rod Cutting Problem | ...
Interleaving String: • Interleaving String | ...
#dp #memoization #topdown
I have been following your channel since leetcode monthly challenge started but never fully explored your channel. I was just watching videos whenever I had doubts about solving some problems. Today I explored all the playlists and checked the content. It's wonderful how you are contributing to the community. In the future, your channel will be one of the best resources for Interview preparation and particularly learning DS and algorithms(it still is but need more impact and viewers). Now I am going to suggest all my juniors to learn from this channel instead of buying any course. Best of luck and thanks for sharing such great content.
Thanks for your motivation 🙂
@@techdose4u can you tell me why it doesn't work
int solve(int l,int r,vector &nums,int x){
if(x
Anyone wondering if it's still giving TLE, please watch the complete video.. (y) 21:35
I was wondering about the solution as I was getting TLE and here you are, I am so lucky to have you over youtube.
😊
When i saw this problem first time i approached it using recursion which is intuitive for this problem.. then i came here.. thank for this video....
Nice. Welcome bro :)
one of the best tutorial for Dp
Sir for this I think we can take left pointer and right pointer and traverse array completely making hashmap of element and count if we find complementary elements we can find minimum count
Yes that's the optimal approach
Not sure the x has a meaning in the calculation of the key for the memoization. If you have left and right indexes the x should always be the same.
This approach is giving TLE if we convert the approach to Java based. Any suggestion to resolve TLE?
Watch the complete video
next video of playlist : ruclips.net/video/7nzwrX4N_A0/видео.html
Nice Explanation ❤❤❤
Thanks
recursion is intiuative in this questions ,but the memoization part can be thought only if you have already seen solution
Leetcode mein TLE a raha hain
Can i use dp[left][right]=count in this manner to store minimum count?
no u need 3 values, x as well.
Nice explanation!
Thanks
@TECH DOSE Can't this problem be solved by making two dimensional table as u have made in your previous videos of DP??
Is there any follow up?
it is better to use pair for memorization
is there a way to apply bottom up in this as memoization is giving tle
bhaiya yeh jo 2 base cases hain unko ooper neeche karne se toh test cases ke galat answer aa rhe hain...par aisa kyon ho rha hai line number 8 ki condition pehle aur line number 6 ki baad mein likhne se wrong output aa rha hai..
It would be great if you can upload leetcode weekly contest solutions
I would love to, but I don't get time 😅
Ok
can greedy approch be used in this question?
amazing sir!!
:)
Can we use dp tabulatio method for this problem?
it is similar to coin change problem 1
Did not get as to why we need the count in making a unique key...could we form a unique state only using left+"*" +right (each are string) ??
Hi Arjun, I think he has concatenated x, so that if user passes the same x multiple times, it will straight away hit memoization value. So successive calls of x will take very little time.
If you take the solution for just one x value, it will not make sense. If this problem was a very small part of a large solution where this block is called multiple times with repeating x values, it will show the true usefulness of concatenating x.
this is giving tle error although explanation is awesome
I did exactly this but still getting heap out of memory exception.
Maybe out of bounds
can i get this code in python
I submitted this question using greedy algorithm
Nice :)
@@techdose4u we can use sliding window technique such a minimum window that sums to target will be our ans.
leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/discuss/939891/Sliding-Window-C%2B%2B
class Solution {
HashMap dp;
int min;
int solve(int [] nums,int l,int r,int x ,int count){
if(x==0)
{
return count;
}
if( l>r || x
You have commented on top MEMOIZATION->TLE ..?
public int minOperations(int[] nums, int x) {
int[] dp = new int[nums.length];
int count = helper(x, nums, 0, nums.length-1, 0, dp);
return count == Integer.MAX_VALUE?-1:count;
}
int helper(int x, int[] arr, int i, int j, int count, int[] dp){
if(xj) return Integer.MAX_VALUE;
if(dp[i]!=0) return dp[i];
return
dp [i] = Math.min( helper(x - arr[i], arr, i+1, j, count+1, dp),
helper (x - arr[j], arr, i, j-1, count+1, dp) );
}
I tried using 2 player stone game technique, but got TLE.
giving tle