🎨 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 o
[\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\n\n---\n\nWe use prefix sums `S` of the input array `A` to calculate each sum of `A` from `i..j` inclusive in O(1) time.  For each player\'s turn there are 2 considerations:\n\n1. Take the right-most value at index `j`\n2. Take the left-most value at index `i`\n\nFor each consideration, we accumulate the sum of the sub-problem from `i..j` inclusive and subtract the sum of the optimal solution to the sub-problem without `j`  xor without `i`.\n* Let `L` be the sum of the sub-problem `i..j - 1` (ie. `i..j` inclusive without `j`) minus the optimal solution to the sub-problem without `j`.\n* Let `R` be the sum of the sub-problem `i + 1..j` (ie. `i..j` inclusive without `i`) minus the optimal solution to the sub-problem without `i`.\n\nThen for the recursive case, we return the maximum of `L` and `R`.  And the base case occurs when `i == j` for which the current player earns `0` points.\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 stoneGameVII(A: IntArray): Int {\n        var N = A.size\n        var S = IntArray(N + 1) { 0 }\n        for (i in 1..N)\n            S[i] = S[i - 1] + A[i - 1]\n        fun go(i: Int = 0, j: Int = N - 1): Int {\n            if (i == j)\n                return 0\n            var L = S[j] - S[i] - go(i, j - 1)\n            var R = S[j + 1] - S[i + 1] - go(i + 1, j)\n            return Math.max(L, R)\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 stoneGameVII(A: IntArray): Int {\n        var m = mutableMapOf<String, Int>()\n        var N = A.size\n        var S = IntArray(N + 1) { 0 }\n        for (i in 1..N)\n            S[i] = S[i - 1] + A[i - 1]\n        fun go(i: Int = 0, j: Int = N - 1): Int {\n            if (i == j)\n                return 0\n            var key = "$i,$j"\n            if (m.contains(key))\n                return m[key]!!\n            var L = S[j] - S[i] - go(i, j - 1)\n            var R = S[j + 1] - S[i + 1] - go(i + 1, j)\n            m[key] = Math.max(L, R)\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 stoneGameVII(A: IntArray): Int {\n        var N = A.size\n        var S = IntArray(N + 1) { 0 }\n        for (i in 1..N)\n            S[i] = S[i - 1] + A[i - 1]\n        var dp = Array(N) { IntArray(N) { 0 } }\n        for (i in N - 2 downTo 0) {\n            for (j in i + 1 until N) {\n                var L = S[j] - S[i] - dp[i][j - 1]\n                var R = S[j + 1] - S[i + 1] - dp[i + 1][j]\n                dp[i][j] = Math.max(L, R)\n            }\n        }\n        return dp[0][N - 1]\n    }\n}\n```\n\n---\n\n**Javascript Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nlet stoneGameVII = A => {\n    let N = A.length;\n    let S = Array(N + 1).fill(0);\n    for (let i = 1; i <= N; ++i)\n        S[i] = S[i - 1] + A[i - 1];\n    let go = (i = 0, j = N - 1) => {\n        if (i == j)\n            return 0;\n        let L = S[j] - S[i] - go(i, j - 1),\n            R = S[j + 1] - S[i + 1] - go(i + 1, j);\n        return Math.max(L, R);\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet stoneGameVII = (A, m = new Map()) => {\n    let N = A.length;\n    let S = Array(N + 1).fill(0);\n    for (let i = 1; i <= N; ++i)\n        S[i] = S[i - 1] + A[i - 1];\n    let go = (i = 0, j = N - 1) => {\n        if (i == j)\n            return 0;\n        let key = `${i},${j}`;\n        if (m.has(key))\n            return m.get(key);\n        let L = S[j] - S[i] - go(i, j - 1),\n            R = S[j + 1] - S[i + 1] - go(i + 1, j);\n        return m.set(key, Math.max(L, R))\n                .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 stoneGameVII = A => {\n    let N = A.length;\n    let S = Array(N + 1).fill(0);\n    for (let i = 1; i <= N; ++i)\n        S[i] = S[i - 1] + A[i - 1];\n    let dp = [...Array(N)].map(_ => Array(N).fill(0));\n    for (let i = N - 2; 0 <= i; --i) {\n        for (let j = i + 1; j < N; ++j) {\n            let L = S[j] - S[i] - dp[i][j - 1],\n                R = S[j + 1] - S[i + 1] - dp[i + 1][j];\n            dp[i][j] = Math.max(L, R);\n        }\n    }\n    return dp[0][N - 1];\n};\n```\n\n---\n\n**Python3 Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\nclass Solution:\n    def stoneGameVII(self, A: List[int]) -> int:\n        N = len(A)\n        S = [0] * (N + 1)\n        for i in range(1, N + 1):\n            S[i] = S[i - 1] + A[i - 1]\n        def go(i = 0, j = N - 1):\n            if i == j:\n                return 0\n            L = S[j] - S[i] - go(i, j - 1)\n            R = S[j + 1] - S[i + 1] - go(i + 1, j)\n            return max(L, R)\n        return go()\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def stoneGameVII(self, A: List[int]) -> int:\n        N = len(A)\n        S = [0] * (N + 1)\n        for i in range(1, N + 1):\n            S[i] = S[i - 1] + A[i - 1]\n        @cache\n        def go(i = 0, j = N - 1):\n            if i == j:\n                return 0\n            L = S[j] - S[i] - go(i, j - 1)\n            R = S[j + 1] - S[i + 1] - go(i + 1, j)\n            return max(L, R)\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 stoneGameVII(self, A: List[int]) -> int:\n        N = len(A)\n        S = [0] * (N + 1)\n        for i in range(1, N + 1):\n            S[i] = S[i - 1] + A[i - 1]\n        dp = [[0] * N for _ in range(N)]\n        for i in range(N - 2, -1, -1):\n            for j in range(i + 1, N):\n                L = S[j] - S[i] - dp[i][j - 1]\n                R = S[j + 1] - S[i + 1] - dp[i + 1][j]\n                dp[i][j] = max(L, R)\n        return dp[0][N - 1]\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 fun = function<int(int, int)>;\n    int stoneGameVII(VI& A) {\n        int N = A.size();\n        VI S(N + 1);\n        for (auto i{ 1 }; i <= N; ++i)\n            S[i] = S[i - 1] + A[i - 1];\n        fun go = [&](auto i, auto j) {\n            if (i == j)\n                return 0;\n            auto L = S[j] - S[i] - go(i, j - 1),\n                 R = S[j + 1] - S[i + 1] - go(i + 1, j);\n            return max(L, R);\n        };\n        return go(0, N - 1);\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 fun = function<int(int, int)>;\n    using Map = unordered_map<string, int>;\n    int stoneGameVII(VI& A, Map m = {}) {\n        int N = A.size();\n        VI S(N + 1);\n        for (auto i{ 1 }; i <= N; ++i)\n            S[i] = S[i - 1] + A[i - 1];\n        fun go = [&](auto i, auto j) {\n            if (i == j)\n                return 0;\n            stringstream key; key << i << "," << j;\n            if (m.find(key.str()) != m.end())\n                return m[key.str()];\n            auto L = S[j] - S[i] - go(i, j - 1),\n                 R = S[j + 1] - S[i + 1] - go(i + 1, j);\n            return m[key.str()] = max(L, R);\n        };\n        return go(0, N - 1);\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 stoneGameVII(VI& A) {\n        int N = A.size();\n        VI S(N + 1);\n        for (auto i{ 1 }; i <= N; ++i)\n            S[i] = S[i - 1] + A[i - 1];\n        VVI dp(N, VI(N, 0));\n        for (auto i{ N - 2 }; 0 <= i; --i) {\n            for (auto j{ i + 1 }; j < N; ++j) {\n                auto L = S[j] - S[i] - dp[i][j - 1],\n                     R = S[j + 1] - S[i + 1] - dp[i + 1][j];\n                dp[i][j] = max(L, R);\n            }\n        }\n        return dp[0][N - 1];\n    }\n};\n```
[]