🎨 The ART of Dynamic Programming
\uD83C\uDFA8 The ART of dynamic programming\n\n1. All possibilities are considered via brute-force top-down depth-first-search\n2. Remember each subproblems\' o
[\uD83C\uDFA8 The **ART** of dynamic programming](https://leetcode.com/discuss/general-discussion/712010/the-art-of-dynamic-programming-an-intuitive-approach-from-apprentice-to-master/)\n\n1. **A**ll possibilities are considered via brute-force top-down depth-first-search\n2. **R**emember each subproblems\' optimal solution via a DP memo\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n4. Memory optimization from O(N<sup>2</sup>) to O(N) by replacing `dp` matrix with previous/current rows\n\n---\n\n**Kotlin Solutions:**\n\n1. **A**ll possibilities are considered via brute-force top-down depth-first-search\n```\nclass Solution {\n    fun minDistance(s: String, t: String): Int {\n        var (M, N) = listOf(s.length, t.length)\n        fun go(i: Int = 0, j: Int = 0): Int {\n            if (i == M || j == N)\n                return M - i + N - j\n            var a = (if (s[i] != t[j]) 1 else 0) + go(i + 1, j + 1)\n            var b = 1 + go(i + 1, j)\n            var c = 1 + go(i, j + 1)\n            return listOf(a, b, c).min()!!\n        }\n        return go()\n    }\n}\n```\n\n2. **R**emember each subproblems\' optimal solution via a DP memo\n```\nclass Solution {\n    fun minDistance(s: String, t: String): Int {\n        var (M, N) = listOf(s.length, t.length)\n        var m = mutableMapOf<String, Int>()\n        fun go(i: Int = 0, j: Int = 0): Int {\n            if (i == M || j == N)\n                return M - i + N - j\n            var k = "$i,$j"\n            if (!m.contains(k)) {\n                var a = (if (s[i] != t[j]) 1 else 0) + go(i + 1, j + 1)\n                var b = 1 + go(i + 1, j)\n                var c = 1 + go(i, j + 1)\n                m[k] = listOf(a, b, c).min()!!\n            }\n            return m[k]!!\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 minDistance(s: String, t: String): Int {\n        var (M, N) = listOf(s.length, t.length)\n        var dp = Array(M + 1) { IntArray(N + 1) { 0 } }\n        for (i in 1..M) dp[i][0] = 1 + dp[i - 1][0]\n        for (j in 1..N) dp[0][j] = 1 + dp[0][j - 1]\n        for (i in 1..M) {\n            for (j in 1..N) {\n                var a = (if (s[i - 1] != t[j - 1]) 1 else 0) + dp[i - 1][j - 1]\n                var b = 1 + dp[i - 1][j]\n                var c = 1 + dp[i][j - 1]\n                dp[i][j] = listOf(a, b, c).min()!!\n            }\n        }\n        return dp[M][N]\n    }\n}\n```\n\n4. Memory optimization from O(N<sup>2</sup>) to O(N) by replacing `dp` matrix with previous/current rows\n```\nclass Solution {\n    fun minDistance(s: String, t: String): Int {\n        var (M, N) = listOf(s.length, t.length)\n        var cur = IntArray(N + 1) { 0 }\n        for (j in 1..N) cur[j] = 1 + cur[j - 1]\n        for (i in 1..M) {\n            var pre = cur.copyOf()\n            ++cur[0]\n            for (j in 1..N) {\n                var a = (if (s[i - 1] != t[j - 1]) 1 else 0) + pre[j - 1]\n                var b = 1 + pre[j]\n                var c = 1 + cur[j - 1]\n                cur[j] = listOf(a, b, c).min()!!\n            }\n        }\n        return cur[N]\n    }\n}\n```\n\n---\n\n**Javascript Solutions:**\n\n1. **A**ll possibilities are considered via brute-force top-down depth-first-search\n```\nlet minDistance = (s, t) => {\n    let [M, N] = [s.length, t.length];\n    let go = (i = 0, j = 0) => {\n        if (i == M || j == N)\n            return M - i + N - j;\n        let a = Number(s[i] != t[j]) + go(i + 1, j + 1),\n            b = 1 + go(i + 1, j),\n            c = 1 + go(i, j + 1);\n        return Math.min(a, b, c);\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblems\' optimal solution via a DP memo\n```\nlet minDistance = (s, t, m = new Map()) => {\n    let [M, N] = [s.length, t.length];\n    let go = (i = 0, j = 0) => {\n        if (i == M || j == N)\n            return M - i + N - j;\n        let k = `${i},${j}`;\n        if (!m.has(k)) {\n            let a = Number(s[i] != t[j]) + go(i + 1, j + 1),\n                b = 1 + go(i + 1, j),\n                c = 1 + go(i, j + 1);\n            m.set(k, Math.min(a, b, c));\n        }\n        return m.get(k);\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet minDistance = (s, t, m = new Map()) => {\n    let [M, N] = [s.length, t.length];\n    let dp = [...Array(M + 1)].map(_ => Array(N + 1).fill(0));\n    for (let i = 1; i <= M; ++i) dp[i][0] = 1 + dp[i - 1][0];\n    for (let j = 1; j <= N; ++j) dp[0][j] = 1 + dp[0][j - 1];\n    for (let i = 1; i <= M; ++i) {\n        for (let j = 1; j <= N; ++j) {\n            let a = Number(s[i - 1] != t[j - 1]) + dp[i - 1][j - 1],\n                b = 1 + dp[i - 1][j],\n                c = 1 + dp[i][j - 1];\n            dp[i][j] = Math.min(a, b, c);\n        }\n    }\n    return dp[M][N];\n};\n```\n\n4. Memory optimization from O(N<sup>2</sup>) to O(N) by replacing `dp` matrix with previous/current rows\n```\nlet minDistance = (s, t, m = new Map()) => {\n    let [M, N] = [s.length, t.length];\n    let cur = Array(N + 1).fill(0);\n    for (let j = 1; j <= N; ++j) cur[j] = 1 + cur[j - 1];\n    for (let i = 1; i <= M; ++i) {\n        let pre = [...cur];\n        ++cur[0];\n        for (let j = 1; j <= N; ++j) {\n            let a = Number(s[i - 1] != t[j - 1]) + pre[j - 1],\n                b = 1 + pre[j],\n                c = 1 + cur[j - 1];\n            cur[j] = Math.min(a, b, c);\n        }\n    }\n    return cur[N];\n};\n```\n\n---\n\n**Python3 Solutions:**\n\n1. **A**ll possibilities are considered via brute-force top-down depth-first-search\n```\nclass Solution:\n    def minDistance(self, s: str, t: str) -> int:\n        M, N = len(s), len(t)\n        def go(i = 0, j = 0):\n            if i == M or j == N:\n                return M - i + N - j\n            a = int(s[i] != t[j]) + go(i + 1, j + 1)\n            b = 1 + go(i + 1, j)\n            c = 1 + go(i, j + 1)\n            return min(a, b, c)\n        return go()\n```\n\n2. **R**emember each subproblems\' optimal solution via a DP memo\n```\nclass Solution:\n    def minDistance(self, s: str, t: str) -> int:\n        M, N = len(s), len(t)\n        @cache\n        def go(i = 0, j = 0):\n            if i == M or j == N:\n                return M - i + N - j\n            a = int(s[i] != t[j]) + go(i + 1, j + 1)\n            b = 1 + go(i + 1, j)\n            c = 1 + go(i, j + 1)\n            return min(a, b, c)\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 minDistance(self, s: str, t: str) -> int:\n        M, N = len(s), len(t)\n        dp = [[0] * (N + 1) for _ in range(M + 1)]\n        for i in range(1, M + 1): dp[i][0] = 1 + dp[i - 1][0]\n        for j in range(1, N + 1): dp[0][j] = 1 + dp[0][j - 1]\n        for i in range(1, M + 1):\n            for j in range(1, N + 1):\n                a = int(s[i - 1] != t[j - 1]) + dp[i - 1][j - 1]\n                b = 1 + dp[i - 1][j]\n                c = 1 + dp[i][j - 1]\n                dp[i][j] = min(a, b, c)\n        return dp[M][N]\n```\n\n4. Memory optimization from O(N<sup>2</sup>) to O(N) by replacing `dp` matrix with previous/current rows\n```\nclass Solution:\n    def minDistance(self, s: str, t: str) -> int:\n        M, N = len(s), len(t)\n        cur = [0] * (N + 1)\n        for j in range(1, N + 1): cur[j] = 1 + cur[j - 1]\n        for i in range(1, M + 1):\n            pre = cur[:]\n            cur[0] += 1\n            for j in range(1, N + 1):\n                a = int(s[i - 1] != t[j - 1]) + pre[j - 1]\n                b = 1 + pre[j]\n                c = 1 + cur[j - 1]\n                cur[j] = min(a, b, c)\n        return cur[N]\n```\n\n---\n\n**C++ Solutions:**\n\n1. **A**ll possibilities are considered via brute-force top-down depth-first-search\n```\nclass Solution {\npublic:\n    using fun = function<int(int, int)>;\n    int minDistance(string s, string t) {\n        int M = s.size(),\n            N = t.size();\n        fun go = [&](auto i, auto j) {\n            if (i == M || j == N)\n                return M - i + N - j;\n            auto a = int(s[i] != t[j]) + go(i + 1, j + 1),\n                 b = 1 + go(i + 1, j),\n                 c = 1 + go(i, j + 1);\n            return min({ a, b, c });\n        };\n        return go(0, 0);\n    }\n};\n```\n\n2. **R**emember each subproblems\' optimal solution via a DP memo\n```\nclass Solution {\npublic:\n    using fun = function<int(int, int)>;\n    using Map = unordered_map<string, int>;\n    int minDistance(string s, string t, Map m = {}) {\n        int M = s.size(),\n            N = t.size();\n        auto key = [](auto i, auto j) {\n            stringstream ss; ss << i << "," << j;\n            return ss.str();\n        };\n        fun go = [&](auto i, auto j) {\n            if (i == M || j == N)\n                return M - i + N - j;\n            auto k = key(i, j);\n            if (m.find(k) == m.end()) {\n                auto a = int(s[i] != t[j]) + go(i + 1, j + 1),\n                     b = 1 + go(i + 1, j),\n                     c = 1 + go(i, j + 1);\n                m[k] = min({ a, b, c });\n            }\n            return m[k];\n        };\n        return go(0, 0);\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 minDistance(string s, string t) {\n        int M = s.size(),\n            N = t.size();\n        VVI dp(M + 1, VI(N + 1));\n        for (auto i{ 1 }; i <= M; ++i) dp[i][0] = 1 + dp[i - 1][0];\n        for (auto j{ 1 }; j <= N; ++j) dp[0][j] = 1 + dp[0][j - 1];\n        for (auto i{ 1 }; i <= M; ++i) {\n            for (auto j{ 1 }; j <= N; ++j) {\n                auto a = int(s[i - 1] != t[j - 1]) + dp[i - 1][j - 1],\n                     b = 1 + dp[i - 1][j],\n                     c = 1 + dp[i][j - 1];\n                dp[i][j] = min({ a, b, c });\n            }\n        }\n        return dp[M][N];\n    }\n};\n```\n\n4. Memory optimization from O(N<sup>2</sup>) to O(N) by replacing `dp` matrix with previous/current rows\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    int minDistance(string s, string t) {\n        int M = s.size(),\n            N = t.size();\n        VI cur(N + 1);\n        for (auto j{ 1 }; j <= N; ++j) cur[j] = 1 + cur[j - 1];\n        for (auto i{ 1 }; i <= M; ++i) {\n            auto pre{ cur };\n            ++cur[0];\n            for (auto j{ 1 }; j <= N; ++j) {\n                auto a = int(s[i - 1] != t[j - 1]) + pre[j - 1],\n                     b = 1 + pre[j],\n                     c = 1 + cur[j - 1];\n                cur[j] = min({ a, b, c });\n            }\n        }\n        return cur[N];\n    }\n};\n```\n\n---\n\n**Legacy Solutions from October 2, 2020:**\n\nLet `i` and `j` be non-inclusive indexes of strings `A` and `B` which denote each corresponding substring of `A[0..i)` and `B[0..j)`.  Let `M` and `N` be the length of `A` and `B`.  Thus initially `i = M` and `j = N` (ie. `A == A[0..i=M)` and `B == B[0..j=N)`).  Recursively consider the last character of `A` and `B`, ie. `A[i - 1]` and `B[j - 1]`, there are 4 use cases:\n\n1. If the last characters match, then there is no penalty, move onto the sub-problems without the last characters\n2. If the last characters mismatch, then the last character in `A` can be replaced with the last character in `B` xor the last character in `B` can be replaced with the last character in `A` to make these characters match.  This replacement is an arbitrary choice with penalty of `1`\n3. If the last characters mismatch, then we can insert a character in `A` xor we can delete a character from `B`.  The insertion/deletion is an arbitrary choice with penalty of `1`\n4. If the last characters mismatch, then we can insert a character in `B` xor we can delete a character from `A`.  The insertion/deletion is an arbitrary choice with penalty of `1`\n\n---\n\n**Example use case 1:** the last character `x` is a match.  There is no penalty.\n```\nA = ...x\nB = ...x\n```\n\n**Example use case 2:** the last character `x` is a mismatch.  Regardless of the arbitrary "fix" choosen, there is a penalty of `1` for this replacement.\n```\nA = ...x\nB = ...y\n```\n\n* If we replace `x` with `y` in `A`, then this use case 2 mismatch is "fixed" as follows:\n```\nA = ...y\nB = ...y\n```\n\n* If we replace `y` with `x` in `B`, then this use case 2 mismatch is "fixed" as follows:\n```\nA = ...x\nB = ...x\n```\n\n**Example use case 3:** the last character `z` is a mismatch.  Regardless of the arbitrary "fix" choosen, there is a penalty of `1` for this insertion/deletion.\n```\nA = xy\nB = xyz\n```\n\n* If we insert `z` in `A`, then this use case 3 mismatch is "fixed" as follows:\n```\nA = xyz\nB = xyz\n```\n\n* If we delete `z` from `B`, then this use case 3 mismatch is "fixed" as follows:\n```\nA = xy\nB = xy\n```\n\n**Example use case 4:** the last character `z` is a mismatch.  Regardless of the arbitrary "fix" choosen, there is a penalty of `1` for this insertion/deletion.\n```\nA = xyz\nB = xy\n```\n\n* If we insert `z` in `B`, then this use case 3 mismatch is "fixed" as follows:\n```\nA = xyz\nB = xyz\n```\n\n* If we delete `z` from `A`, then this use case 3 mismatch is "fixed" as follows:\n```\nA = xy\nB = xy\n```\n\n---\n\n**Javascript Solutions:**\n\n*Javascript: Top-Down TLE without Memo*\n```\nlet minDistance = (A, B) => {\n    let go = (A, B, i, j) => {\n        if (!i || !j)\n            return i + j; // \uD83D\uDED1 base case: we have exhausted A or B, return "leftover" distance\n        return Math.min(\n            go(A, B, i - 1, j - 1) + Number(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n            go(A, B, i - 1, j) + 1, // \u274C insertion\n            go(A, B, i, j - 1) + 1  // \u274C deletion\n        );\n    };\n    return go(A, B, A.length, B.length);\n};\n```\n\n*Javascript: Top-Down with Memo*\n```\nlet minDistance = (A, B) => {\n    let go = (A, B, i, j, memo = {}) => {\n        let key = `${i},${j}`; // \uD83D\uDD11 \n        if (memo[key])\n            return memo[key]; // \uD83E\uDD14 memo\n        if (!i || !j)\n            return memo[key] = i + j; // \uD83D\uDED1 base case: we have exhausted A or B, return "leftover" distance\n        return memo[key] = Math.min(\n            go(A, B, i - 1, j - 1, memo) + Number(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n            go(A, B, i - 1, j, memo) + 1, // \u274C insertion \n            go(A, B, i, j - 1, memo) + 1  // \u274C deletion\n        );\n    };\n    return go(A, B, A.length, B.length);\n};\n```\n\n*Javascript: Bottom-Up with full DP matrix*\n```\nlet minDistance = (A, B) => {\n    let [M, N] = [A.length, B.length];\n    let dp = [...Array(M + 1)].map(row => Array(N + 1).fill(0)); // \uD83E\uDD14 memo\n    for (let i = 0; i <= M; ++i) dp[i][0] = i; // \uD83D\uDED1 base case: we have exhausted B, return "leftover" distance\n    for (let j = 0; j <= N; ++j) dp[0][j] = j; // \uD83D\uDED1 base case: we have exhausted A, return "leftover" distance\n    for (let i = 1; i <= M; ++i)\n        for (let j = 1; j <= N; ++j)\n            dp[i][j] = Math.min(\n                dp[i - 1][j - 1] + Number(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n                dp[i - 1][j] + 1, // \u274C insertion \n                dp[i][j - 1] + 1, // \u274C deletion\n            );\n    return dp[M][N];\n};\n```\n\n*Javascript: Bottom-Up with memory optimization to only store previous and current rows of the DP matrix*\n```\nlet minDistance = (A, B) => {\n    let [M, N] = [A.length, B.length];\n    let pre = [...Array(N + 1)].map((_, i) => i); // \uD83E\uDD14 memo \uD83D\uDED1 base case: we have exhausted A or B, return "leftover" distance\n    for (let i = 1; i <= M; ++i) {\n        let cur = [...pre]; // \uD83E\uDD14 generate current from previous\n        cur[0] = i; // \uD83D\uDED1 base case: we have exhausted A or B, return "leftover" distance\n        for (let j = 1; j <= N; ++j) {\n            cur[j] = Math.min(\n                pre[j - 1] + Number(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n                pre[j] + 1,     // \u274C insertion \n                cur[j - 1] + 1, // \u274C deletion\n            );\n        }\n        [pre, cur] = [cur, pre]; // swap\n    }\n    return pre[N];\n};\n```\n\n---\n\n**C++ Solutions:**\n\n*C++: Top-Down TLE without Memo*\n```\nclass Solution {\npublic:\n    int minDistance(string A, string B) {\n        return go(A, B, A.size(), B.size());\n    }\nprivate:\n    int go(string& A, string& B, int i, int j) {\n        if (!i || !j)\n            return i + j; // \uD83D\uDED1 base case: we have exhausted A or B, return "leftover" distance\n        return min({\n            go(A, B, i - 1, j - 1) + int(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n            go(A, B, i - 1, j) + 1, // \u274C insertion\n            go(A, B, i, j - 1) + 1  // \u274C deletion\n        });\n    }\n};\n```\n\n*C++: Top-Down with Memo*\n```\nclass Solution {\npublic:\n    int minDistance(string A, string B) {\n        return go(A, B, A.size(), B.size());\n    }\nprivate:\n    using Memo = unordered_map<string, int>;\n    int go(string& A, string& B, int i, int j, Memo&& memo = {}) {\n        stringstream ss; ss << i << "," << j;\n        auto key = ss.str(); // \uD83D\uDD11\n        if (memo.find(key) != memo.end())\n            return memo[key]; // \uD83E\uDD14 memo\n        if (!i || !j)\n            return memo[key] = i + j;\n        return memo[key] = min({\n            go(A, B, i - 1, j - 1, move(memo)) + int(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n            go(A, B, i - 1, j, move(memo)) + 1, // \u274C insertion\n            go(A, B, i, j - 1, move(memo)) + 1  // \u274C deletion\n        });\n    }\n};\n```\n\n*C++: Bottom-Up with full DP matrix*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int minDistance(string A, string B) {\n        auto [M, N] = make_tuple(A.size(), B.size());\n        VVI dp(M + 1, VI(N + 1)); // \uD83E\uDD14 memo\n        for (auto i = 0; i <= M; ++i) dp[i][0] = i; // \uD83D\uDED1 base case: we have exhausted B, return "leftover" distance\n        for (auto j = 0; j <= N; ++j) dp[0][j] = j; // \uD83D\uDED1 base case: we have exhausted A, return "leftover" distance\n        for (auto i = 1; i <= M; ++i)\n            for (auto j = 1; j <= N; ++j)\n                dp[i][j] = min({\n                    dp[i - 1][j - 1] + int(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n                    dp[i - 1][j] + 1, // \u274C insertion \n                    dp[i][j - 1] + 1, // \u274C deletion\n                });\n        return dp[M][N];\n    }\n};\n```\n\n*C++: Bottom-Up with memory optimization to only store previous and current rows of the DP matrix*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int minDistance(string A, string B) {\n        auto [M, N] = make_tuple(A.size(), B.size());\n        VI pre(N + 1); // \uD83E\uDD14 memo\n        iota(pre.begin(), pre.end(), 0); // \uD83D\uDED1 base case: we have exhausted A or B, i is the "leftover" distance\n        for (auto i = 1; i <= M; ++i) {\n            auto cur{ pre }; // \uD83E\uDD14 generate current from previous\n            cur[0] = i; // \uD83D\uDED1 base case: we have exhausted A or B, i is the "leftover" distance\n            for (auto j = 1; j <= N; ++j) {\n                cur[j] = min({\n                    pre[j - 1] + int(A[i - 1] != B[j - 1]), // \u2705 match xor \u274C mismatch\n                    pre[j] + 1,     // \u274C insertion \n                    cur[j - 1] + 1, // \u274C deletion\n                });\n            }\n            swap(pre, cur);\n        }\n        return pre[N];\n    }\n};\n```
[]