🎨 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\nAfter considering all possibilities by hand for the first 10 values, one key observation is to greedily consume two 3s over three 2s because we want to maximize the product and for the sum of `6`, and we have two key candidates: `2 * 2 * 2 = 8 < 9 = 3 * 3`\n```\n6 = 2 + 2 + 2  \uD83D\uDC49  2 * 2 * 2 = 8\n\n6 = 3 + 3      \uD83D\uDC49      3 * 3 = 9\n```\n\nWe can then use dynamic programming to greedily construct the `n`<sup>th</sup> best integer break value via the following base case and recurrence relation:\n\n**Base case:**\n\n`dp[i] = i` when `i <= 3`\n\nNote: this is contrary to the optimal solutions when `n <= 3`, so if `n <= 3` we return `n - 1`, ie. if `n == 2` then return `1` and if `n == 3` then return `2`.\n\n**Recurrence relation:**\n\nWe construct each optimal current `i`<sup>th</sup> solution by choosing the maximum of 2 possibilities:\n\n1. the previous optimal solution with sum two away from `i`, ie. `i - 2`, multiplied by `2` \n2. the previous optimal solution with sum three away from `i`, ie. `i - 3`, multipled by `3`\n\nDP formula:\n\n`dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])`\n\n**Visualization:**\n\n![image](https://assets.leetcode.com/users/images/fdb3c316-13b8-4639-b901-59b6ad867c9f_1637456222.828826.png)\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 integerBreak(n: Int): Int {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        fun go(i: Int = n): Int {\n            if (i <= 3)\n                return i\n            return Math.max(2 * go(i - 2), 3 * go(i - 3))\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 integerBreak(n: Int): Int {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        var m = mutableMapOf<Int, Int>()\n        fun go(i: Int = n): Int {\n            if (i <= 3)\n                return i\n            if (!m.contains(i))\n                m[i] = Math.max(2 * go(i - 2), 3 * go(i - 3))\n            return m[i]!!\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 integerBreak(n: Int): Int {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        var dp = IntArray(n + 1) { it }\n        for (i in 4..n)\n            dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3])\n        return dp[n]\n    }\n}\n```\n\n*Bottom-Up -- O(1) Memory via Sliding Window (a, b, c, d \uD83D\uDC48 dp[i - 3], dp[i - 2], dp[i - 1], dp[i])*\n```\nclass Solution {\n    fun integerBreak(n: Int): Int {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        var (a, b, c, d) = IntArray(4) { it + 1 }\n        for (i in 4..n) {\n            d = Math.max(2 * b, 3 * a)  // dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3])\n            a = b; b = c; c = d         // \uD83D\uDC48 slide window\n        }\n        return d\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 integerBreak = n => {\n    if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n        return n - 1;\n    let go = (i = n) => {\n        if (i <= 3)\n            return i;\n        return Math.max(2 * go(i - 2), 3 * go(i - 3));\n    };\n    return go();\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet integerBreak = (n, m = new Map()) => {\n    if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n        return n - 1;\n    let go = (i = n) => {\n        if (i <= 3)\n            return i;\n        if (!m.has(i))\n            m.set(i, Math.max(2 * go(i - 2), 3 * go(i - 3)));\n        return m.get(i);\n    };\n    return go();\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet integerBreak = n => {\n    if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n        return n - 1;\n    let dp = [...Array(n + 1).keys()];\n    for (let i = 4; i <= n; ++i)\n        dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);\n    return dp[n];\n};\n```\n\n*Bottom-Up -- O(1) Memory via Sliding Window (a, b, c, d \uD83D\uDC48 dp[i - 3], dp[i - 2], dp[i - 1], dp[i])*\n```\nlet integerBreak = n => {\n    if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n        return n - 1;\n    let [a, b, c, d] = [...Array(4).keys()].map(it => it + 1);\n    for (let i = 4; i <= n; ++i) {\n        d = Math.max(2 * b, 3 * a);  // dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);\n        a = b, b = c, c = d;         // \uD83D\uDC48 slide window\n    }\n    return d;\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 integerBreak(self, n: int) -> int:\n        if n <= 3:  # \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        def go(i = n):\n            if i <= 3:\n                return i\n            return max(2 * go(i - 2), 3 * go(i - 3))\n        return go()\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n <= 3:  # \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        @cache\n        def go(i = n):\n            if i <= 3:\n                return i\n            return max(2 * go(i - 2), 3 * go(i - 3))\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 integerBreak(self, n: int) -> int:\n        if n <= 3:  # \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        dp = [i for i in range(n + 1)]\n        for i in range(4, n + 1):\n            dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])\n        return dp[n]\n```\n\n*Bottom-Up -- O(1) Memory via Sliding Window (a, b, c, d \uD83D\uDC48 dp[i - 3], dp[i - 2], dp[i - 1], dp[i])*\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n <= 3:  # \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1\n        a, b, c, d = [i + 1 for i in range(4)]\n        for i in range(4, n + 1):\n            d = max(2 * b, 3 * a)  # dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])\n            a = b; b = c; c = d    # \uD83D\uDC48 slide window\n        return d\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 fun = function<int(int)>;\n    int integerBreak(int n) {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1;\n        fun go = [&](auto i) {\n            if (i <= 3)\n                return i;\n            return max(2 * go(i - 2), 3 * go(i - 3));\n        };\n        return go(n);\n    }\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\npublic:\n    using fun = function<int(int)>;\n    using Map = unordered_map<int, int>;\n    int integerBreak(int n, Map m = {}) {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1;\n        fun go = [&](auto i) {\n            if (i <= 3)\n                return i;\n            if (m.find(i) == m.end())\n                m[i] = max(2 * go(i - 2), 3 * go(i - 3));\n            return m[i];\n        };\n        return go(n);\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    int integerBreak(int n) {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1;\n        VI dp(n + 1); iota(dp.begin(), dp.end(), 0);\n        for (auto i{ 4 }; i <= n; ++i)\n            dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3]);\n        return dp[n];\n    }\n};\n```\n\n*Bottom-Up -- O(1) Memory via Sliding Window (a, b, c, d \uD83D\uDC48 dp[i - 3], dp[i - 2], dp[i - 1], dp[i])*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    int integerBreak(int n) {\n        if (n <= 3)  // \u2B50\uFE0F recurrence relation\'s base case != optimal solution\n            return n - 1;\n        auto [a, b, c, d] = make_tuple(1, 2, 3, 4);\n        for (auto i{ 4 }; i <= n; ++i) {\n            d = max(2 * b, 3 * a);  // dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])\n            a = b, b = c, c = d;    // \uD83D\uDC48 slide window\n        }\n        return d;\n    }\n};\n```
[]