Despite years of these puzzle-ish programming problems, I still struggle with DP.
But I have finally discovered how to solve any DP (so far) without cracking my head!
This just works, I have used it a couple times without any problem.
Note: You still need to be able to solve the basic problem! However memoization now becomes very "mechanic".
- Start with a recursive "bruteforce" solution for any problem. (I'm using Go, but you do you)
func solution(a, b, c params) solutionType {
// ... maybe some prework
return actualSolution(a, x, 0, 0)
}
func actualSolution(a, x, y, z params) solutionType {
if someBaseCase {
return someValue
}
// ... non-base case solution here
return actualSolution(a, newX, newY, newZ)
}- We'll assume
actualSolutionwill solve the problem but it's too slow. Add these types anywhere
type dp map[dpKey]dpVal // we'll just throw memory at it
type dpVal = solutionType // type alias but can be different
type dpKey struct { // all DP parameters, like.. "i and j" or "str"
x, y, z int // int, string, bool, whatever the param type is
}- Now just transform the function into a
dpmethod and create adpinstance, look for:change here!
func solution(a, b, c params) solutionType {
// ... maybe some prework
return dp{}.actualSolution(a, x, 0, 0)
// ^-- change here!
}
// v--- change here! v--- change here!
func (dp dp) actualSolution(a, x, y, z params) (_result solutionType) {
// START change here! START
key := dpKey{x,y,z} // if it's a single value don't use a struct
if v, ok := dp[key]; ok {
return v
}
defer func(){ // "defer" in go executes when the function returns, on Java you could use "try/finally"
dp[key] = _result // memoize returned value
}()
// END change here! END
if someBaseCase {
return someValue
}
// ... non-base case solution here
return dp.actualSolution(a, newX, newY, newZ)
// ^--- change here!
}And that's it!
"But what about the
dp[i][j]variable or an iterative solution?"
I just can't reason that way, making it iterative and bottom-up vs top-down is just too hard and annoying for me.
Once I have this solution I can "transform it" into an iterative solution if I so desired, but at the cost of spending a lot of time!
This obviously has its flaws, it's not the best performing, but it gets the job done!