[GoLang] Recursive -> Mem Optimised DP
Intuition\nWe need to find a Min/Max of something in an array/matrix => It\'s a Dynamic Programming problem (rarely a Greedy problem).\n\n# Approach - Simple re
# Intuition\nWe need to find a Min/Max of something in an array/matrix => It\'s a Dynamic Programming problem (rarely a Greedy problem).\n\n# Approach - Simple recursive function\nDon\'t try to write a final optimized code from the start, it will break your mind. Always start with defining a recursive function:\n\n`rec(pile_idx, used) = max_over_j(sum_of_j_coins_from_this_pile + rec(pile_idx + 1, used - j)`\nAnd the answer can be found with `rec(0, k)`\n\nThe following code works fine with small test cases but will hit the TimeLimit if you submit it. Check out the next approach.\n\n\n# Code - Simple recursive function\n```\nfunc maxValueOfCoins(piles [][]int, k int) int {\n    n := len(piles)\n\n    var rec func(int, int) int\n    rec = func(i int, used int) int {\n        if i == n { return 0 }\n        accum := 0\n        res := rec(i+1, used)\n        for j:=0; j<min(len(piles[i]), used); j++ {\n            accum += piles[i][j]\n            res = max(res, accum + rec(i+1, used-j-1))\n        }\n        return res\n    }\n    return rec(0, k)\n}\n\nfunc min(a, b int) int {\n    if a < b { return a }\n    return b\n}\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n```\n\n---\n\n# Approach - Recursive function with Memo\nCreate a memo matrix with size of `len(piles)\u22C5k` and use it for caching `rec()` results. It will pass all test cases.\n\n![Screenshot 2023-04-15 at 14.40.13.png](https://assets.leetcode.com/users/images/2dc8d044-7249-40d1-86b7-62400f33d94f_1681555225.9792976.png)\n\n# Code - Recursive function with Memo\n\n```\nfunc maxValueOfCoins(piles [][]int, k int) int {\n    n := len(piles)\n    memo := make([][]int, n)\n    for i := range memo {\n        memo[i] = make([]int, k+1)\n    }\n\n    var rec func(int, int) int\n    rec = func(i int, used int) int {\n        if i == n { return 0 }\n        if memo[i][used] > 0 { return memo[i][used] }\n        accum := 0\n        res := rec(i+1, used)\n        for j:=0; j<min(len(piles[i]), used); j++ {\n            accum += piles[i][j]\n            res = max(res, accum + rec(i+1, used-j-1))\n        }\n        memo[i][used] = res\n        return res\n    }\n    return rec(0, k)\n}\n\nfunc min(a, b int) int {\n    if a < b { return a }\n    return b\n}\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n```\n\n---\n\n# Approach - Bottom-up DP\nWe understand how our memo matrix must look like and how we can fill it in recursively. Now we need to do the same using loops.\n\nTraverse all `piles` and `used` in a nested loop and change `rec(i+1, used)` into `memo[i+1][used]`. Almost all the code remains the same (that\'s the neat part of this process).\n\n![Screenshot 2023-04-15 at 14.45.07.png](https://assets.leetcode.com/users/images/c84423aa-bdc7-4753-9365-bfdc9ab27d5d_1681555517.5403607.png)\n\n# Code - Bottom-up DP\n\n```\nfunc maxValueOfCoins(piles [][]int, k int) int {\n    n := len(piles)\n    memo := make([][]int, n+1)\n    for i := range memo {\n        memo[i] = make([]int, k+1)\n    }\n\n    for i:=n-1; i>=0; i-- {\n        for used:=0; used<=k; used++ {\n            accum := 0\n            res := memo[i+1][used]\n            for j:=0; j<min(len(piles[i]), used); j++ {\n                accum += piles[i][j]\n                res = max(res, accum + memo[i+1][used-j-1])\n            }\n            memo[i][used] = res\n        }\n    }\n    return memo[0][k]\n}\n\nfunc min(a, b int) int {\n    if a < b { return a }\n    return b\n}\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n```\n\n---\n\n# Approach - Bottom-up Mem Optimised DP\nNotice that we need only the values from `memo[i]` and `memo[i+1]`, so no need to keep the whole matrix in the memory. Just create a one dimensional list `dp` of size `k`.\n\n![Screenshot 2023-04-15 at 15.00.41.png](https://assets.leetcode.com/users/images/82ad0e39-fd25-4e03-a4c8-2dad71573b2b_1681556636.8669186.png)\n\n# Code - Bottom-up Mem Optimised DP\n\n```\nfunc maxValueOfCoins(piles [][]int, k int) int {\n    n := len(piles)\n    dp := make([]int, k+1)\n\n    for i:=n-1; i>=0; i-- {\n        for used:=k; used>=0; used-- {\n            accum := 0\n            res := dp[used]\n            for j:=0; j<min(len(piles[i]), used); j++ {\n                accum += piles[i][j]\n                res = max(res, accum + dp[used-j-1])\n            }\n            dp[used] = res\n        }\n    }\n    return dp[k]\n}\n\nfunc min(a, b int) int {\n    if a < b { return a }\n    return b\n}\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n```\n\n### Do some code optimisations\n\n```\nfunc maxValueOfCoins(piles [][]int, k int) int {\n    dp := make([]int, k+1)\n\n    for i := range piles {\n        for used:=k; used>=0; used-- {\n            accum := 0\n            for j:=0; j<min(len(piles[i]), used); j++ {\n                accum += piles[i][j]\n                dp[used] = max(dp[used], accum + dp[used-j-1])\n            }\n        }\n    }\n    return dp[k]\n}\n\nfunc min(a, b int) int {\n    if a < b { return a }\n    return b\n}\nfunc max(a, b int) int {\n    if a > b { return a }\n    return b\n}\n```\n\n\n# Complexity\n- Time complexity: $$O(totalCoinsNum\u22C5k)$$\n\n- Space complexity: $$O(k)$$
['Array', 'Dynamic Programming', 'Recursion', 'Matrix', 'Go']