🎨  The ART of Dynamic Programming
\uD83C\uDFA8  The ART of Dynamic Programming\n\n1. All possibilities are considered via top-down brute-force depth-first-search\n2. Remember each subproblem\'s 
[\uD83C\uDFA8  The ART of Dynamic Programming](https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master)\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n\nRecursively include each `j`<sup>th</sup> value of each `i`<sup>th</sup> row of the input matrix `A` onto a running total `t` to consider each candidate `cand` in order to find the `best` candidate for each `i`<sup>th</sup> row.  Then we have 2 choices for each each `i`<sup>th</sup> row\'s `best` candidate:\n\n1. \u2705 include\n2. \uD83D\uDEAB exclude\n\nOptimally choose the maximum at each `i`<sup>th</sup> sub-problem to formulate the overall optimal solution as the recursive stack unwinds.\n\n**Note:** the problem statement\'s image is misleading, ie. "buckets" are drawn as columns, however, the "buckets" are actually stored in the input matrix `A` as rows.\n\n---\n\n**Kotlin Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution {\n    fun maxValueOfCoins(A: List<List<Int>>, K: Int): Int {\n        var M = A.size\n        fun go(i: Int = 0, k: Int = K): Int {\n            if (i == M || k == 0)\n                return 0\n            var (t, best) = Pair(0, 0)\n            for (j in 0 until Math.min(A[i].size, k)) {\n                t += A[i][j]\n                var cand = t + go(i + 1, k - 1 - j)\n                best = Math.max(best, cand)\n            }\n            return Math.max(best, go(i + 1, k)) // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        }\n        return go()\n    }\n}\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\n    fun maxValueOfCoins(A: List<List<Int>>, K: Int): Int {\n        var M = A.size\n        var m = mutableMapOf<String, Int>()\n        fun go(i: Int = 0, k: Int = K): Int {\n            if (i == M || k == 0)\n                return 0\n            var key = "$i,$k"\n            if (!m.contains(key)) {\n                var (t, best) = Pair(0, 0)\n                for (j in 0 until Math.min(A[i].size, k)) {\n                    t += A[i][j]\n                    var cand = t + go(i + 1, k - 1 - j)\n                    best = Math.max(best, cand)\n                }\n                m[key] = Math.max(best, go(i + 1, k)) // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n            return m[key]!!\n        }\n        return go()\n    }\n}\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution {\n    fun maxValueOfCoins(A: List<List<Int>>, K: Int): Int {\n        var M = A.size\n        var dp = Array(M + 1) { IntArray(K + 1 ) { 0 } }\n        for (i in M - 1 downTo 0) {\n            for (k in 1..K) {\n                var (t, best) = Pair(0, 0)\n                for (j in 0 until Math.min(A[i].size, k)) {\n                    t += A[i][j]\n                    var cand = t + dp[i + 1][k - 1 - j]\n                    best = Math.max(best, cand)\n                }\n                dp[i][k] = Math.max(best, dp[i + 1][k]) // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n        }\n        return dp[0][K]\n    }\n}\n```\n\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n```\nclass Solution {\n    fun maxValueOfCoins(A: List<List<Int>>, K: Int): Int {\n        var M = A.size\n        var pre = IntArray(K + 1) { 0 }\n        for (i in M - 1 downTo 0) {\n            var cur = IntArray(K + 1) { 0 }\n            for (k in 1..K) {\n                var (t, best) = Pair(0, 0)\n                for (j in 0 until Math.min(A[i].size, k)) {\n                    t += A[i][j]\n                    var cand = t + pre[k - 1 - j]\n                    best = Math.max(best, cand)\n                }\n                cur[k] = Math.max(best, pre[k]) // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n            pre = cur\n        }\n        return pre[K]\n    }\n}\n```\n\n---\n\n**Javascript Solutions:**\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nlet maxValueOfCoins = (A, K) => {\n    let M = A.length;\n    let go = (i = 0, k = K) => {\n        if (i == M || !k)\n            return 0;\n        let [t, best] = [0, 0];\n        for (let j = 0; j < Math.min(A[i].length, k); ++j) {\n            t += A[i][j];\n            let cand = t + go(i + 1, k - 1 - j);\n            best = Math.max(best, cand);\n        }\n        return Math.max(best, go(i + 1, k)); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet maxValueOfCoins = (A, K, m = new Map()) => {\n    let M = A.length;\n    let go = (i = 0, k = K) => {\n        if (i == M || !k)\n            return 0;\n        let key = `${i},${k}`;\n        if (!m.has(key)) {\n            let [t, best] = [0, 0];\n            for (let j = 0; j < Math.min(A[i].length, k); ++j) {\n                t += A[i][j];\n                let cand = t + go(i + 1, k - 1 - j);\n                best = Math.max(best, cand);\n            }\n            m.set(key, Math.max(best, go(i + 1, k))); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        }\n        return m.get(key);\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet maxValueOfCoins = (A, K) => {\n    let M = A.length;\n    let dp = [...Array(M + 1)].map(_ => Array(K + 1).fill(0));\n    for (let i = M - 1; 0 <= i; --i) {\n        for (let k = 1; k <= K; ++k) {\n            let [t, best] = [0, 0];\n            for (let j = 0; j < Math.min(A[i].length, k); ++j) {\n                t += A[i][j];\n                let cand = t + dp[i + 1][k - 1 - j];\n                best = Math.max(best, cand);\n            }\n            dp[i][k] = Math.max(best, dp[i + 1][k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        }\n    }\n    return dp[0][K];\n};\n```\n\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n```\nlet maxValueOfCoins = (A, K) => {\n    let M = A.length;\n    let pre = Array(K + 1).fill(0);\n    for (let i = M - 1; 0 <= i; --i) {\n        let cur = Array(K + 1).fill(0);\n        for (let k = 1; k <= K; ++k) {\n            let [t, best] = [0, 0];\n            for (let j = 0; j < Math.min(A[i].length, k); ++j) {\n                t += A[i][j];\n                let cand = t + pre[k - 1 - j];\n                best = Math.max(best, cand);\n            }\n            cur[k] = Math.max(best, pre[k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        }\n        pre = cur;\n    }\n    return pre[K];\n};\n```\n\n---\n\n**Python3 Solutions:**\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution:\n    def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:\n        M = len(A)\n        def go(i = 0, k = K):\n            if i == M or not k:\n                return 0\n            t, best = 0, 0\n            for j in range(0, min(len(A[i]), k)):\n                t += A[i][j]\n                cand = t + go(i + 1, k - 1 - j)\n                best = max(best, cand)\n            return max(best, go(i + 1, k)) # \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        return go()\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:\n        M = len(A)\n        @cache\n        def go(i = 0, k = K):\n            if i == M or not k:\n                return 0\n            t, best = 0, 0\n            for j in range(0, min(len(A[i]), k)):\n                t += A[i][j]\n                cand = t + go(i + 1, k - 1 - j)\n                best = max(best, cand)\n            return max(best, go(i + 1, k)) # \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        return go()\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution:\n    def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:\n        M = len(A)\n        dp = [[0] * (K + 1) for _ in range(M + 1)]\n        for i in range(M - 1, -1, -1):\n            for k in range(K, -1, -1):\n                t, best = 0, 0\n                for j in range(0, min(len(A[i]), k)):\n                    t += A[i][j]\n                    cand = t + dp[i + 1][k - 1 - j]\n                    best = max(best, cand)\n                dp[i][k] = max(best, dp[i + 1][k]) # \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        return dp[0][K]\n```\n\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n```\nclass Solution:\n    def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:\n        M = len(A)\n        pre = [0] * (K + 1)\n        for i in range(M - 1, -1, -1):\n            cur = [0] * (K + 1)\n            for k in range(K, -1, -1):\n                t, best = 0, 0\n                for j in range(0, min(len(A[i]), k)):\n                    t += A[i][j]\n                    cand = t + pre[k - 1 - j]\n                    best = max(best, cand)\n                cur[k] = max(best, pre[k]) # \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            pre = cur\n        return pre[K]\n```\n\n---\n\n**Rust Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\n// TODO: how to write recursive closure in Rust which captures the parent\'s scope?\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\n// TODO: how to write recursive closure in Rust which captures the parent\'s scope?\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\ntype VI = Vec<i32>;\ntype VVI = Vec<VI>;\nuse std::cmp::min;\nuse std::cmp::max;\nimpl Solution {\n    pub fn max_value_of_coins(A: VVI, K_: i32) -> i32 {\n        let M = A.len();\n        let K = K_ as usize;\n        let mut dp = vec![vec![0; K + 1]; M + 1];\n        for i in (0..M).rev() {\n            for k in 1..=K {\n                let (mut t, mut best) = (0, 0);\n                for j in 0..min(A[i].len(), k) {\n                    t += A[i][j];\n                    let cand = t + dp[i + 1][k - 1 - j];\n                    best = max(best, cand);\n                }\n                dp[i][k] = max(best, dp[i + 1][k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n        }\n        return dp[0][K];\n    }\n}\n```\n\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n```\ntype VI = Vec<i32>;\ntype VVI = Vec<VI>;\nuse std::cmp::min;\nuse std::cmp::max;\nimpl Solution {\n    pub fn max_value_of_coins(A: VVI, K_: i32) -> i32 {\n        let M = A.len();\n        let K = K_ as usize;\n        let mut pre = vec![0; K + 1];\n        for i in (0..M).rev() {\n            let mut cur = vec![0; K + 1];\n            for k in 1..=K {\n                let (mut t, mut best) = (0, 0);\n                for j in 0..min(A[i].len(), k) {\n                    t += A[i][j];\n                    let cand = t + pre[k - 1 - j];\n                    best = max(best, cand);\n                }\n                cur[k] = max(best, pre[k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n            pre = cur;\n        }\n        return pre[K];\n    }\n}\n```\n\n---\n\n**C++ Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    using fun = function<int(int, int)>;\n    int maxValueOfCoins(VVI& A, int K) {\n        int M = A.size();\n        fun go = [&](auto i, auto k) {\n            if (i == M || !k)\n                return 0;\n            auto [t, best] = make_pair(0, 0);\n            for (auto j{ 0 }; j < min((int)A[i].size(), k); ++j) {\n                t += A[i][j];\n                auto cand = t + go(i + 1, k - 1 - j);\n                best = max(best, cand);\n            }\n            return max(best, go(i + 1, k)); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n        };\n        return go(0, K);\n    }\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    using fun = function<int(int, int)>;\n    using Map = unordered_map<string, int>;\n    int maxValueOfCoins(VVI& A, int K, Map m = {}) {\n        int M = A.size();\n        auto hash = [](auto i, auto k) {\n            stringstream ss; ss << i << "," << k;\n            return ss.str();\n        };\n        fun go = [&](auto i, auto k) {\n            if (i == M || !k)\n                return 0;\n            auto key = hash(i, k);\n            if (m.find(key) == m.end()) {\n                auto [t, best] = make_pair(0, 0);\n                for (auto j{ 0 }; j < min((int)A[i].size(), k); ++j) {\n                    t += A[i][j];\n                    auto cand = t + go(i + 1, k - 1 - j);\n                    best = max(best, cand);\n                }\n                m[key] = max(best, go(i + 1, k)); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n            return m[key];\n        };\n        return go(0, K);\n    }\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int maxValueOfCoins(VVI& A, int K) {\n        int M = A.size();\n        VVI dp(M + 1, VI(K + 1));\n        for (auto i{ M - 1 }; 0 <= i; --i) {\n            for (auto k{ 1 }; k <= K; ++k) {\n                auto [t, best] = make_pair(0, 0);\n                for (auto j{ 0 }; j < min((int)A[i].size(), k); ++j) {\n                    t += A[i][j];\n                    auto cand = t + dp[i + 1][k - 1 - j];\n                    best = max(best, cand);\n                }\n                dp[i][k] = max(best, dp[i + 1][k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n        }\n        return dp[0][K];\n    }\n};\n```\n\n4. Memory optimization (ie. we only need the previous row to formulate the current row)\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int maxValueOfCoins(VVI& A, int K) {\n        int M = A.size();\n        VI pre(K + 1);\n        for (auto i{ M - 1 }; 0 <= i; --i) {\n            VI cur(K + 1);\n            for (auto k{ 1 }; k <= K; ++k) {\n                auto [t, best] = make_pair(0, 0);\n                for (auto j{ 0 }; j < min((int)A[i].size(), k); ++j) {\n                    t += A[i][j];\n                    auto cand = t + pre[k - 1 - j];\n                    best = max(best, cand);\n                }\n                cur[k] = max(best, pre[k]); // \u2705 include or \uD83D\uDEAB exclude i-th row\'s best candidate\n            }\n            pre = cur;\n        }\n        return pre[K];\n    }\n};\n```
[]