DP
https://leetcode.com/problems/target-sum/solutions/455024/dp-is-easy-5-steps-to-think-through-dp-questions/ First i have to use recursion to the question then i have to go for memoization and then last i will go for top down approaches. How to find the base case? Think of the smallest valid input. if(n==0 || w==0) return 0 as the smallest n would be 0 and also the weight for 0/1 knapsack would be 0 as well, we can not take negative weight on a bag. if i go to a store and the store has all the bigger items then i can not hold it to the bag so weight would be 0. similarly if the store has no item so n=0 Recursive function: fn (i/p) fn(smaller i/p) if the input is n then we have to go for (n-1) as the smaller input as that will work as recursion. 0/1 Knapsack Problem: 416. Partition Equal Subset Sum 474. Ones and Zeroes 494. Target Sum 1049. Last Stone Weight II 879. Profitable Schemes 1155. Number of Dice Rolls With Target Sum Unbounded Knapsack Prob...