🎨 The ART of Dynamic Programming
Game Plan\n\n## \uD83C\uDFA8 The ART of Dynamic Programming:\n\n### DFS + Memo to optimally choose the maximum of 3 possibilities per i..j search-space of the i
# Game Plan\n\n## [\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\n### DFS + Memo to optimally choose the maximum of 3 possibilities per `i..j` search-space of the input array `A`\n\n* **a)** Choose the first two elements of nums and delete them.\n* **b)** Choose the last two elements of nums and delete them.\n* **c)** Choose the first and the last elements of nums and delete them.\n\n# Code\n\n![bi-contest124.png](https://assets.leetcode.com/users/images/4c1d2c01-99d4-4bda-a590-ba4ccfc98bb0_1708187152.7770982.png)\n\n*Kotlin*\n```\nclass Solution {\n    fun maxOperations(A: IntArray): Int {\n        var N = A.size\n        var dp = Array(N){ IntArray(N){ -1} }\n        fun go(i: Int = 0, j: Int = N - 1, last: Int = 0): Int {\n            if (j <= i)\n                return 0\n            if (dp[i][j] == -1) {\n                var a = if (last == 0 || last == A[i] + A[i + 1]) 1 + go(i + 2, j, A[i] + A[i + 1]) else 0\n                var b = if (last == 0 || last == A[j - 1] + A[j]) 1 + go(i, j - 2, A[j - 1] + A[j]) else 0\n                var c = if (last == 0 || last == A[i] + A[j]) 1 + go(i + 1, j - 1, A[i] + A[j]) else 0\n                dp[i][j] = listOf(a, b, c).max()\n            }\n            return dp[i][j]\n        }\n        return go()\n    }\n}\n```\n\n*Javascript*\n```\nlet maxOperations = (A, N = A.length, dp = [...Array(N)].map(_ => Array(N).fill(-1))) => {\n    let go = (i = 0, j = N - 1, last = 0) => {\n        if (j <= i)\n            return 0;\n        if (dp[i][j] != -1)\n            return dp[i][j];\n        let a = (!last || last == A[i] + A[i + 1]) ? 1 + go(i + 2, j, A[i] + A[i + 1]) : 0,\n            b = (!last || last == A[j - 1] + A[j]) ? 1 + go(i, j - 2, A[j - 1] + A[j]) : 0,\n            c = (!last || last == A[i] + A[j]) ? 1 + go(i + 1, j - 1, A[i] + A[j]) : 0;\n        return dp[i][j] = Math.max(a, b, c);\n    };\n    return go();\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def maxOperations(self, A: List[int]) -> int:\n        @cache\n        def go(i = 0, j = len(A) - 1, last = 0):\n            if j <= i:\n                return 0\n            a = 1 + go(i + 2, j, A[i] + A[i + 1]) if not last or last == A[i] + A[i + 1] else 0\n            b = 1 + go(i, j - 2, A[j - 1] + A[j]) if not last or last == A[j - 1] + A[j] else 0\n            c = 1 + go(i + 1, j - 1, A[i] + A[j]) if not last or last == A[i] + A[j] else 0\n            return max(a, b, c)\n        return go()\n```\n\n*Rust*\n```\ntype VI = Vec<i32>;\ntype VVI = Vec<VI>;\nimpl Solution {\n    pub fn max_operations(A: VI) -> i32 {\n        let N = A.len();\n        let mut dp = vec![vec![-1; N]; N];\n        fn go(A: &VI, i: i32, j: i32, last: i32, dp: &mut VVI) -> i32 {\n            if j <= i {\n                return 0;\n            }\n            if dp[i as usize][j as usize] == -1 {\n                let a = if last == 0 || last == A[i as usize] + A[i as usize + 1] { 1 + go(A, i + 2, j, A[i as usize] + A[i as usize + 1], dp) } else { 0 };\n                let b = if last == 0 || last == A[j as usize- 1] + A[j as usize] { 1 + go(A, i, j - 2, A[j as usize - 1] + A[j as usize], dp) } else { 0 };\n                let c = if last == 0 || last == A[i as usize] + A[j as usize] { 1 + go(A, i + 1, j - 1, A[i as usize] + A[j as usize], dp) } else { 0 };\n                dp[i as usize][j as usize] = vec![a, b, c].into_iter().max().unwrap();\n            }\n            dp[i as usize][j as usize]\n        }\n        go(&A, 0, N as i32 - 1, 0, &mut dp)\n    }\n}\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    using fun = function<int(int, int, int)>;\n    int maxOperations(VI& A) {\n        int N = A.size();\n        VVI dp(N, VI(N, -1));\n        fun go = [&](auto i, auto j, auto last) {\n            if (j <= i)\n                return 0;\n            if (dp[i][j] != -1)\n                return dp[i][j];\n            auto a = (!last || last == A[i] + A[i + 1]) ? 1 + go(i + 2, j, A[i] + A[i + 1]) : 0,\n                 b = (!last || last == A[j - 1] + A[j]) ? 1 + go(i, j - 2, A[j - 1] + A[j]) : 0,\n                 c = (!last || last == A[i] + A[j]) ? 1 + go(i + 1, j - 1, A[i] + A[j]) : 0;\n            return dp[i][j] = max({a, b, c});\n        };\n        return go(0, N - 1, 0);\n    }\n};\n```\n\n---\n\n# Supplemental: \uD83C\uDF5E "Breadcrumbs" for how we arrived "here" \uD83C\uDFAF\n```\n# Submission Result: Wrong Answer \n# Input:\n# [1,9,7,3,2,7,4,12,2,6]\n# Output:\n# 3\n# Expected:\n# 2\n\n# class Solution:\n#     def maxOperations(self, A: List[int]) -> int:\n#         N = len(A)\n#         @cache\n#         def go(i = 0, j = N - 1, last = 0):\n#             if j <= i:\n#                 return 0\n#             a = go(i + 2, j, A[i] + A[i + 1]) if not last or last == A[i] + A[i + 1] else 0\n#             b = go(i, j - 2, A[j - 1] + A[j]) if not last or last == A[j - 1] + A[j] else 0\n#             c = go(i + 1, j - 1, A[i] + A[j]) if not last or last == A[i] + A[j] else 0\n#             return 1 + max(a, b, c)\n#         return go()\n\n# Game Plan\n# [\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\n# Use DFS + Memo to optimally choose from 3 possibilities:\n\n# a. Choose the first two elements of nums and delete them.\n# b. Choose the last two elements of nums and delete them.\n# c. Choose the first and the last elements of nums and delete them.\n\n# # Implementations\n# *Python3*\nclass Solution:\n    def maxOperations(self, A: List[int]) -> int:\n        N = len(A)\n        @cache\n        def go(i = 0, j = N - 1, last = 0):\n            if j <= i:\n                return 0\n            a = 1 + go(i + 2, j, A[i] + A[i + 1]) if not last or last == A[i] + A[i + 1] else 0\n            b = 1 + go(i, j - 2, A[j - 1] + A[j]) if not last or last == A[j - 1] + A[j] else 0\n            c = 1 + go(i + 1, j - 1, A[i] + A[j]) if not last or last == A[i] + A[j] else 0\n            return max(a, b, c)\n        return go()\n\n# this is kinda silly, right?\n\n# class Solution:\n#     def maxOperations(self, A: List[int], T = 2000, best = 0) -> int:\n#         N = len(A)\n#         dp = [[[0] * (T + 1) for _ in range(N)] for _ in range(N)]\n#         for last in range(T + 1):\n#             for i in range(N):\n#                 for j in reversed(range(i + 1, N)):\n#                     a = 1 + (dp[i + 2][j][A[i] + A[i + 1]] if i + 2 < N else 0) if not last or (i + 1 < N and last == A[i] + A[i + 1]) else 0\n#                     b = 1 + (dp[i][j - 2][A[j - 1] + A[j]] if 0 <= j - 2 else 0) if not last or (0 <= j - 1 and last == A[j - 1] + A[j]) else 0\n#                     c = 1 + (dp[i + 1][j - 1][A[i] + A[j]] if 0 <= j - 1 and i + 1 < N else 0) if not last or last == A[i] + A[j] else 0\n#                     dp[i][j][last] = max(a, b, c)\n#                     best = max(best, dp[i][j][last])\n#         return best\n```
['C++', 'Python3', 'Rust', 'Kotlin', 'JavaScript']