You will be further directed to DP-17 when you watch DP-18 . This series is very well designed !

@immortal6978

8 ай бұрын

Its Recursion Go back and complete the part to get answer. Higher Problem to lower subproblems

@solitucedagar4298

16 күн бұрын

@@immortal6978 🤣

I would have never thought, it can also be solved like this🤯. Thanks for this awesome playlist striver❤

damn man ! been watching all the videos of this playlist from the beginning, this is the best video so far !! and you striver. You are not only teaching how to do DP, but indeed how to think DP ! Kudos to you for this playlist.

Damn man ! been watching all the videos of this playlist from the beginning, this is the best video so far !! and you Striver. You are not only teaching how to do DP, but indeed how to think DP ! Kudos to you for this playlist.💌💌💌💌

I would have never thought of approaching this problem this way. Superb! Thanks for this. I have watched and solved all the videos till now in this series. Longest Common Subsequence and Longest Increasing Subsequence are much awaited.

Before watching your tutorial , I did solve this problem 🙂 using map(the naive recursive way and optimized with map). Here's the solution : int f(int i, int target, vector& nums, unordered_map& dp) { if (i == nums.size()) { if (target == 0) return 1; return 0; } string key = to_string(i) + "_" + to_string(target); if (dp.find(key) != dp.end()) return dp[key]; int ways = f(i + 1, target - nums[i], nums, dp) + f(i + 1, target + nums[i], nums, dp); dp[key] = ways; return ways; } int findTargetSumWays(vector& nums, int target) { unordered_map dp; return f(0, target, nums, dp); }

as soon as you wrote those S1 and S2 i figured out ohh hell yess this can be done by that approach! Best one till now!

plus minus way. int solve(int ind,int target,vector &nums,map &dp) { if(ind { //either you achieve the target or you don't achieve the target if(target == 0) return 1; else return 0; } if(dp.find({ind, target}) != dp.end()) { return dp[{ind,target}]; } int plus = 0; int minus = 0; plus = solve(ind-1,target + nums[ind],nums,dp); minus = solve(ind - 1, target - nums[ind],nums,dp); return dp[{ind, target}] = plus + minus; } int findTargetSumWays(vector& nums, int target) { map dp; return solve(nums.size()-1,target,nums,dp); }

@samnoitall9799

3 ай бұрын

if we use a vector instead of a map it doesnt work can you please tell why

@dhruvmohata7528

3 ай бұрын

@@samnoitall9799 because we have a negative values so we can't put them in vector as we cant have -ve indexes

@priyanshkumariitd

26 күн бұрын

​@@samnoitall9799 negative values

Completed till here, please upload more videos. Thank you for such a quality content.

for 2:30 to 2:50 you said exactly what everyone was thinking 😂😂

Thanks striver. I solved this using normal recursion but you helped me to recognise the pattern of this problem.

Damn Damn Damn striver ,was not able to think that this question can be solved using this way.Mapping of problems is very much important.

wow!!!!! awesome explanation, you are gods gift to the coding community🙏🙏🙏🙏🙏

In this question the target value can also be negative so it'll be better to take the min of sum+ target and sum - target as the length of prev and curr just because of the fact that, if target is negative then sum + target will be smaller than sum - target 😊

I never thought I could solve a dp problem :)...thanks legend!

😮😮😮Watching this solution made me go waahh!!!! Thank you bhaiya!!

Very nice study approaches. Thank you for this.

just fantastic. really getting enjoyed and feeling interested in coding and problem solving after your vidoes and approach sir. Thank you sir

understood bhai , thank you soo much for this entire dp series and all other dsa series as well;

The thought process is great bruh

What will be the base case for target as there target can be -1000 to 1000 so how he handles the negative values

I was just studying from ur previous videos and got new♥️

BEST TEACHER EVERRRRR!!!

how to modify the memoization solution if the target is negative.??

Understood. Thankyou Sir

understood at its best..

Omg i made this problem for Coding ninjas

@shubhdangwal4190

4 ай бұрын

you baited me man kudos to u !

chumeshwari explanation bhayia 🥰🥰🥰

why totsum-d should be even, incase of odd directly return false?

You're genius man. Understood very well.

terminate called after throwing an instance of 'std::length_error' what(): cannot create std::vector larger than max_size() I am gettting this error in leet code

understood thank you so much

Understood very well

Hey Striver, In problem: L3. Longest Word With All Prefixes | Complete String | Trie in Trie Series, you gave c++ solution in java solution link. Can you please provide java solution?

Revision done. Was confused in the beginning: I had falsely assumed elements to be negative and thus took time to get to the point. Nov'13, 2023 05:25 pm

did it on my own, thnx

Understoood so damn well 🔥🔥🔥🔥

I solved this problem yesterday and by considering +,- combinations, definitely had space complexity problems. This video gave me a different direction to think this same problem. Thank you!

@gauravpoharkar9797

Жыл бұрын

give me recusion solution bro Im unable to do it .

@ok-jg9jb

Жыл бұрын

@@gauravpoharkar9797 f(ind, tar) { if(ind==0) if(tar+a[0]==0||tar-a[0]==0) Return 1 Else Retun 0 Plus=f(ind-1, a[ind]+tar) Minus=f(ind-1, a[ind]-tar) Return plus+minus

@siddharth892

6 ай бұрын

@@gauravpoharkar9797 For the recursion + Memoisation I think a better way would be to use a dictionary rather than the array because of the negative indexes specially in python since It will start indexing from the back.

Target is negative here too. Run time error nhi dega?

amazing understood

UNDERSTOOD... ! Thanks striver for the video... :)

Once again I was able to solve it on my own. Thank you Striver

Incredible 😮

plus + negative method of recursion is not working by my code, can anyone let me know the code of it

Hi..Can you tell that are there cases where memorization will give TLE but not tabulation?

@udayprakashharsh2805

Жыл бұрын

In memoization we basicaaly use recussion to call function right, So when we perform calls then we need to ressign variables for each call and calling each function takes a lot more time. so memo o(n) >> tab o(n) Always Just because of function calls it takes more time.

Understood! I appreciate for your amazing explanation!!

Thank You Understood!

UNDERSTOOD, thank you very much 😍

understood!!😀😀😀

int[] a = {1,2,3,1} target = 3 private static int getCount1(int[] a, int target, int length) { if(target == 0){ return 1; } if(length == -1 ){ return 0; } int pos = getCount1(a, a[length]-target, length-1); int neg = getCount1(a, -a[length]-target, length-1); return neg + pos; } with this code I am able to solve the pblm but if i try to apply memoization in this dp[arr.length][target+1] then there is a pblm where target can go in negative. (-4, -1, -2....) so will get ArrayIndexOutOfBounds -4 for dp[length][target] . any idea how to solve this kind of pblms

@pranavm002

Жыл бұрын

for such cases you need double the size of the arr

understood!!

Bro, this time understood the ""problem"" more clearly than solution :D. I read somewhere that understanding the problem well is like problem half solved. You are explaining same in multiple ways. I remember the same incidence from Codestudio contest from last week.

@ka.patelhimeyatulkumar19ba58

2 жыл бұрын

bhaiyaa aap hai naa aditya verma ka dekhiye acche se samjaya hai. mast hai.

@lapimpale

2 жыл бұрын

@@ka.patelhimeyatulkumar19ba58 free me ad? Me Jo bola wo samajho pehle fir advice dena

UNDERSTOOOOOOD.

this is also solution for the same class Solution { public: int sol(vector& nums, int target,int ind,int curr) { if(ind==0) { if(target==curr && nums[0]==0) return 2; if(target==curr+nums[0] || target==curr-nums[0] ) return 1; return 0; } int pos=sol(nums,target,ind-1,curr+nums[ind]); int neg=sol(nums,target,ind-1,curr-nums[ind]); return pos+neg; } int findTargetSumWays(vector& nums, int target) { int n=nums.size(); // vector return sol(nums,target,n-1,0); } };

@aayushbisht4307

Жыл бұрын

thanks man! I was missing this return condition

@shivasai7707

Жыл бұрын

@@aayushbisht4307 bruh what will be memorization matrix size

@naveenramadheni2482

Жыл бұрын

@@shivasai7707 May be memorization is not possible becoz curr will go to negative in some recursive calls

@GoldyAwad

Жыл бұрын

@@naveenramadheni2482 We can memoize it using unordered_map, instead of a 2d vector, use vector

@naveenramadheni2482

Жыл бұрын

@@GoldyAwad Bro that idea is really good bro. (now got it that how to memoize -ve indexes)

Can anyone correct my solution: int f(int i,int t,vector&arr){ if(i==0){ if(abs(t)==arr[0])return 1; else return 0; } int neg=f(i-1,t+arr[i],arr); int pos=f(i-1,t-arr[i],arr); return neg+pos; } int targetSum(int n, int target, vector& arr) { return f(n-1,target,arr); } it is going wrong when arr starts with 0.But I dont know y and how to rectify this.

Nice! Understood ❤.

if i do this probelm in this way pick or not pick is it wrong? because we have to count the ways to return the given target. int ways(int target, int i, vector& arr) { if (i == 0) { if (target == arr[0]) return 1; return -1; } if (target == 0) return 1; int take = 0; if (target >= arr[i]) { int takeResult = ways(target - arr[i], i - 1, arr); take = (takeResult == -1) ? 0 : 1 + takeResult; } int notTake = 0; int notTakeResult = ways(target, i - 1, arr); notTake = (notTakeResult == -1) ? 0 : 1 + notTakeResult; return take + notTake; }

s1-s2=target , man striver is the guyyy!!!!

Understood ❤

Please make a vedio on binary lifting algorithm for kth ancestor in BT. Not much is available on KZread. Thanks in advance. 🙏🙏

Pure genius 👌

Understood bro ✌✌ and once again the power of observation is shown 🤩🔥🔥

can anyone pls help me? I am using the recursive approach , where I am either adding the current element to sum or subtracting the current element. and returning 1 when target == sum this is the approach:- int help(int n,int target,int sum ,vector&arr){ if(target == sum){ return 1; } if (n == 0){ return 0; } int ans = help(n-1,target,sum - arr[n - 1],arr); ans += help(n - 1,target,sum + arr[n-1],arr); return ans; } int targetSum(int n, int target, vector& arr) { return help(n,target,0,arr); } thanks in advance for the help

Understood!

Understoood

Superb yarrrrrrrr

Understood!!

MindBlowingggggg

understood!

Understood...Completed (21/56)

Wow it’s a tricky approach

understood :)❤

understood , you are the best teacher

awesome

understood , outstanding explanation on this video !

negative positive soln f(idx, tar): //base case:- if(idx==0) if(arr(idx)+tar == 0 || arr(idx)-tar == 0) return 1; // logic and recursive call int neg = f(idx-1, tar - (-arr(i))); int pos = f(idx-1, tar - arr(i)); return neg+pos; Time complexity: O(2^N) as every element has 2 options either positive or negative

Striver bhaiya "Maximum profit in Job Scheduling" waala question explain kijiyegaa na and DP+Binary Search type waale questions explain kijiyegaa naa. Thanks for DP series!!

Understood!!😇

Understood !!!!!

understood

Understood

genius !!!

Striver bhaiya i was nnot able to comment in last vedio. I was saying that in DP-20 we can do further optimizations too as we have done in 0/1 knapsack by just using a single array reducing the SC to O(target+1)

@takeUforward

2 жыл бұрын

Yes.

@arindamdongre4143

11 ай бұрын

how?

@arindamdongre4143

11 ай бұрын

I am gettig wrong answer by using only one array

Please bhaiya reply... I am getting a huge tention in my mind about my branch (electrical engineering) in Haldia Institute of Technology that weather my branch will stop my success or do electrical engineering students gets equal opportunity in 'big IT companies'?

understood very well❤❤❤

Understood, sir. Thank you very much.

Kudos to your intuition thanks striver

it becomes complicated when there are 0s in input arrays. because they can go to any of two subsets.

@akshaygill4692

Жыл бұрын

I think just returning 2 in case of 0 would work

UNDERSTOOD

Understood !!'

great

Understood :) ...

Understood Thanks you so much!

Hii sir! Why this approach is not working in Leetcode's Target Sum problem? Can anyone tell me the memoization approach of leet code's Target sum problem and what is the difference between this and that problem?

@abhishekgururani6993

2 жыл бұрын

because in leetcode there are test cases in which target is a -ve number.

@Steve-kv5we

Жыл бұрын

It is working fine in leetcode u must have done something wrong.

@mohansharma1989

Жыл бұрын

I tried this way in LC public int findTargetSumWays(int[] nums, int target) { Map dp = new HashMap(); return findTargetSumWaysBottomUpMemoization(nums, nums.length - 1, target, dp); } private int findTargetSumWaysBottomUpMemoization(int[] nums, int index, int target, Map dp) { if (index == 0) { if (target == 0 && nums[0] == 0) { return 2; } else if (target + nums[0] == 0 || target - nums[0] == 0) return 1; else return 0; } String key = index + "-" + target; if (dp.containsKey(key)) return dp.get(key); int minus = findTargetSumWaysBottomUpMemoization(nums, index - 1, target - nums[index], dp); int plus = findTargetSumWaysBottomUpMemoization(nums, index - 1, target + nums[index], dp); int count = minus + plus; dp.put(key, count); return count; } But struggling to convert to tabulation

@anshumaan1024

Жыл бұрын

this is memoization soln class Solution { public: int f(int ind, int target, vector &nums, vector &dp){ if(ind==0){ if(nums[0]==0 && target==0) return 2; if(target==0 || nums[0]==target) return 1; else return 0; } if(dp[ind][target]!= -1) return dp[ind][target]; int notTake = f(ind-1,target,nums,dp); int take = 0; if(nums[ind]

@lavkushdas5529

Жыл бұрын

@@anshumaan1024 Thanks bro , i was not updating dp matrix according to new target

Big Brain...

Awesome observation

The only thing that demotivates in dp if somewhere I need to think out of the box and I feel I'm not that smart.

Understood, thanks!

int f(int ind,int target,vector& arr){ if(ind==0){ if(arr[0]==target || arr[0]==(-target)) return 1; return 0; } int plus = f(ind-1,target-arr[ind],arr); int minus = f(ind-1,target+arr[ind],arr); return plus+minus; } Can anyone tell when i convert this into memoization im getting wrong answer. And also i took size of dp array as int sum = 0; for(int i=0;i

@shashankkumar5005

11 ай бұрын

same problem bro

@shashankkumar5005

11 ай бұрын

actually here the target can be negative at any point making dp[index][negative]

@gyanp_28

11 ай бұрын

Here when we call the function through minus the problem arises because the target can become negative too and the 2-d dp array is working from 0-> target hence it will give index out of bound error One possible solution can be using memoization only when the target>=0 through this we can avoid the error but the code willnt be fully optimised

@karthikk2316

5 ай бұрын

in the base case add one more condiitoin if(arr[0]==target &&arr[0]==(-target))return 2; before the or used base condition

If the target is negative then what should we do ?

@pranavm002

Жыл бұрын

use map as instead of vector as dp map dp;