Lets say knapsack. In an interview, would you implement the recursive backtracking approach with memoization that keeps path if val is better than previous optimal or iterative dp and backtrack the dp table constructing the path? #leetcode #interviews
Recursive + memorization. Then sometimes when you have the top down approach, you can see the tabulated approach as the code almost draws out the optimized recursive relation and base cases
Sorry bro but I can’t seem to see the dp solution probably why I’m not at Faang lool, could someone elaborate or paste some code. The recursive + memoization solution is straightforward though
Something along the lines of Start at i =n-1 If dp[i]>dp[i-1] + val[i-1] then val[i-1] cannot be in our optimal path so we dont jump to dp[i-1] otherwise yes.
Nah fam you’re good. DP is actually not that bad compared to some other problems cause you can just do backtracking which is the workhorse of DP problems. For example in word break, consider the backtracking solution where you consider the partial solution from your string to index i. If s[:i] is valid, then perform a backtracking on the remainder string s[i+1]. If that recursion call for the remainder is true, you’re good otherwise return the recursive call to the next index i+1. It’s hard to explain in words: Backtrack(s) If len(s) = 0: Return true since all the characters have been used for a valid string that I’ve processed in an early call to this func Else if s in memo: I already processed this string in some other sub tree and it was false (otherwise we wouldn’t be here!) Memorize s For each substr in s: If substr in wordDict and backtrack(remainder) is true: Return true Return false since no substring is valid or you can’t generate a valid set from the remainder
You got to do DP otherwise you are looking at exponential time algorithm
Hey so I tried out a dp implementation could someone check it. Only tested a few cases. Bottom up dp approach with union concept to save space rather than build structure for every point in array. https://onlinegdb.com/H13m2X5XL
Bottom up with space efficiency was pretty rough though doubt I can come up with this in interview setting where I’d have to justify each step. Backtrack with memo seems like the way to go.
I always prefer top-down with memoization for interview simplicity though in reality its not efficient
Recursive backtracking + memorization. How would you backtrack dp table? DP table is built bottom up, no going back
Start from end, backtrack optimal path till the beginning
Make another table and keep track of decisions you took for each cell.