🎨 The ART of Dynamic Programming
\uD83C\uDFA8 The ART of Dynamic Programming\n\nLet dp[j] denote the optimal earnings ending at index j.  There are 2 possibilties to consider for each jth endin
[\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\nLet `dp[j]` denote the optimal earnings ending at index `j`.  There are 2 possibilties to consider for each `j`<sup>th</sup> ending position\'s intervals:\n\n* **Case 1:** *include* the interval `i..j` with tip `k`\n* **Case 2:** *exclude* the interval `i..j` with tip `k`\n\nWhen we *include* the interval `i..j`, we add the interval\'s earnings onto the previous optimal earnings ending at index `i` inclusive.\nWhen we *exclude* the interval `i..j`, we update the current optimal earnings ending at `j` to the previous optimal earnings ending at `j - 1`.\n\n**Similar Problem:** [1235. Maximum Profit in Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/1477025/The-ART-of-Dynamic-Programming)\n\n---\n\n*Kotlin*\n```\nclass Solution {\n    fun maxTaxiEarnings(N: Int, A: Array<IntArray>): Long {\n        var dp = LongArray(N + 1) { 0 }\n        var m = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()\n        for ((i, j, k) in A) {\n            if (!m.contains(j))\n                m[j] = mutableListOf<Pair<Int, Int>>()\n            m[j]!!.add(Pair(i, k))\n        }\n        for (j in 1..N) {\n            if (!m.contains(j)) {\n                dp[j] = dp[j - 1]\n                continue\n            }\n            for ((i, k) in m[j]!!) {\n                var include = dp[i] + j - i + k\n                var exclude = dp[j - 1]\n                dp[j] = listOf(dp[j], include, exclude).max()!!\n            }\n        }\n        return dp[N]\n    }\n}\n```\n\n*Javascript*\n```\nlet maxTaxiEarnings = (N, A, m = new Map()) => {\n    let dp = Array(N + 1).fill(0);\n    for (let [i, j, k] of A) {\n        if (!m.has(j))\n            m.set(j, []);\n        m.get(j).push([i, k]);\n    }\n    for (let j = 1; j <= N; ++j) {\n        if (!m.has(j)) {\n            dp[j] = dp[j - 1];\n            continue;\n        }\n        for (let [i, k] of m.get(j)) {\n            let include = dp[i] + j - i + k,\n                exclude = dp[j - 1];\n            dp[j] = Math.max(dp[j], include, exclude);\n        }\n    }\n    return dp[N];\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def maxTaxiEarnings(self, N: int, A: List[List[int]]) -> int:\n        m = {}\n        for i, j, k in A:\n            if j not in m:\n                m[j] = []\n            m[j].append([i, k])\n        dp = [0] * (N + 1)\n        for j in range(1, N + 1):\n            if j not in m:\n                dp[j] = dp[j - 1]\n                continue\n            for i, k in m[j]:\n                include = dp[i] + j - i + k\n                exclude = dp[j - 1]\n                dp[j] = max(dp[j], include, exclude)\n        return dp[N]\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using LL = long long;\n    using VL = vector<LL>;\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    using Pair = pair<int, int>;\n    using Pairs = vector<Pair>;\n    using Map = unordered_map<int, Pairs>;\n    LL maxTaxiEarnings(int N, VVI& A, Map m = {}) {\n        VL dp(N + 1);\n        for (auto& ride: A) {\n            auto [i, j, k] = tie(ride[0], ride[1], ride[2]);\n            m[j].emplace_back(i, k);\n        }\n        for (auto j{ 1 }; j <= N; ++j) {\n            if (m.find(j) == m.end()) {\n                dp[j] = dp[j - 1];\n                continue;\n            }\n            for (auto [i, k]: m[j]) {\n                LL include = dp[i] + j - i + k,\n                   exclude = dp[j - 1];\n                dp[j] = max({ dp[j], include, exclude });\n            }\n        }\n        return dp[N];\n    }\n};\n```
[]