🎨 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\nFor each candidate root `x` of the input array `A`, consider `x = y * z` where `y` and `z` are candidates for the left/right subtrees of `x`, ie. we use the rule-of-product to accumulate the count `cnt` of subtrees, initially set to 1 for `x` as a tree comprised of a single root node.\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 numFactoredBinaryTrees(A: IntArray, MOD: Long = (1e9 + 7).toLong()): Int {\n        var N = A.size\n        var seen = A.toSet()\n        fun go(x: Int): Long {\n            var cnt = 1L\n            for (y in A) {\n                if (x % y != 0)\n                    continue\n                var z = x / y\n                if (seen.contains(z))\n                    cnt = (cnt + (go(y) * go(z) % MOD)) % MOD\n            }\n            return cnt\n        }\n        var t = 0L\n        for (x in A)\n            t = (t + go(x)) % MOD\n        return t.toInt()\n    }\n}\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\n    fun numFactoredBinaryTrees(A: IntArray, MOD: Long = (1e9 + 7).toLong()): Int {\n        var N = A.size\n        var seen = A.toSet()\n        var m = mutableMapOf<Int, Long>()\n        fun go(x: Int): Long {\n            if (!m.contains(x)) {\n                var cnt = 1L\n                for (y in A) {\n                    if (x % y != 0)\n                        continue\n                    var z = x / y\n                    if (seen.contains(z))\n                        cnt = (cnt + (go(y) * go(z) % MOD)) % MOD\n                }\n                m[x] = cnt\n            }\n            return m[x]!!\n        }\n        var t = 0L\n        for (x in A)\n            t = (t + go(x)) % MOD\n        return t.toInt()\n    }\n}\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution {\n    fun numFactoredBinaryTrees(A: IntArray, MOD: Long = (1e9 + 7).toLong()): Int {\n        var N = A.size\n        var seen = A.toSet()\n        var m = mutableMapOf<Int, Long>()\n        for (x in A)\n            m[x] = 1L\n        A.sort()\n        for (x in A) {\n            for (y in A) {\n                if (x % y != 0)\n                    continue\n                var z = x / y\n                if (z in seen)\n                    m[x] = (m[x]!! + (m[y]!! * m[z]!! % MOD)) % MOD\n            }\n        }\n        var t = 0L\n        for ((_, cnt) in m)\n            t = (t + cnt) % MOD\n        return t.toInt()\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 numFactoredBinaryTrees = (A, seen = new Set(A), MOD = Number(1e9 + 7), t = 0) => {\n    let go = x => {\n        let cnt = 1;\n        for (let y of A) {\n            if (x % y)\n                continue;\n            let z = Math.floor(x / y);\n            if (seen.has(z))\n                cnt = (cnt + go(y) * go(z) % MOD) % MOD;\n        }\n        return cnt;\n    };\n    for (let x of A)\n        t = (t + go(x)) % MOD;\n    return t;\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nlet numFactoredBinaryTrees = (A, seen = new Set(A), MOD = Number(1e9 + 7), m = new Map(), t = 0) => {\n    let go = x => {\n        if (!m.has(x)) {\n            let cnt = 1;\n            for (let y of A) {\n                if (x % y)\n                    continue;\n                let z = Math.floor(x / y);\n                if (seen.has(z))\n                    cnt = (cnt + go(y) * go(z) % MOD) % MOD;\n            }\n            m.set(x, cnt);\n        }\n        return m.get(x);\n    };\n    for (let x of A)\n        t = (t + go(x)) % MOD;\n    return t;\n};\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nlet numFactoredBinaryTrees = (A, seen = new Set(A), MOD = Number(1e9 + 7), m = new Map(), t = 0) => {\n    A.sort((a, b) => a - b);\n    for (let x of A)\n        m.set(x, 1);\n    for (let x of A) {\n        for (let y of A) {\n            if (x % y)\n                continue;\n            let z = Math.floor(x / y);\n            if (seen.has(z))\n                m.set(x, m.get(x) + (m.get(y) * m.get(z) % MOD) % MOD);\n        }\n    }\n    for (let [_, cnt] of m)\n        t = (t + cnt) % MOD;\n    return t;\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 numFactoredBinaryTrees(self, A: List[int], MOD = int(1e9 + 7), t = 0) -> int:\n        seen = set(A)\n        def go(x):\n            cnt = 1\n            for y in A:\n                if x % y:\n                    continue\n                z = x // y\n                if z in seen:\n                    cnt = (cnt + (go(y) * go(z) % MOD)) % MOD\n            return cnt\n        for x in A:\n            t = (t + go(x)) % MOD\n        return t\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution:\n    def numFactoredBinaryTrees(self, A: List[int], MOD = int(1e9 + 7), t = 0) -> int:\n        seen = set(A)\n        @cache\n        def go(x):\n            cnt = 1\n            for y in A:\n                if x % y:\n                    continue\n                z = x // y\n                if z in seen:\n                    cnt = (cnt + (go(y) * go(z) % MOD)) % MOD\n            return cnt\n        for x in A:\n            t = (t + go(x)) % MOD\n        return t\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\nclass Solution:\n    def numFactoredBinaryTrees(self, A: List[int], MOD = int(1e9 + 7)) -> int:\n        seen = set(A)\n        m = {x: 1 for x in A}\n        A.sort()\n        for x in A:\n            for y in A:\n                if x % y:\n                    continue\n                z = x // y\n                if z in seen:\n                    m[x] = (m[x] + (m[y] * m[z] % MOD)) % MOD\n        return sum(m.values()) % MOD\n```\n\n---\n\n**Rust Solutions:**\n\n1. **A**ll possibilities are considered via top-down brute-force depth-first-search\n```\ntype VI = Vec<i32>;\nuse std::collections::HashSet;\nimpl Solution {\n    pub fn num_factored_binary_trees(A: VI) -> i32 {\n        let seen: HashSet<i32> = A.clone().into_iter().collect();\n        fn go(A: &VI, x: i32, seen: &HashSet<i32>) -> i64 {\n            let MOD = (1e9 as i64 + 7);\n            let mut cnt = 1 as i64;\n            for y in A {\n                if x % y != 0 {\n                    continue;\n                }\n                let z = x / y;\n                if seen.contains(&z) {\n                    cnt = (cnt + go(A, *y, seen) * go(A, z, seen) % MOD) % MOD;\n                }\n            }\n            return cnt;\n        }\n        let mut t = 0 as i64;\n        for x in &A {\n            t = (t + go(&A, *x, &seen)) % (1e9 as i64 + 7);\n        }\n        return t as i32;\n    }\n}\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\ntype VI = Vec<i32>;\nuse std::collections::{HashMap, HashSet};\nimpl Solution {\n    pub fn num_factored_binary_trees(A: VI) -> i32 {\n        let seen: HashSet<i32> = A.clone().into_iter().collect();\n        let mut m = HashMap::new();\n        fn go(A: &VI, x: i32, seen: &HashSet<i32>, m: &mut HashMap<i32, i64>) -> i64 {\n            if !m.contains_key(&x) {\n                let MOD = (1e9 as i64 + 7);\n                let mut cnt = 1 as i64;\n                for y in A {\n                    if x % y != 0 {\n                        continue;\n                    }\n                    let z = x / y;\n                    if seen.contains(&z) {\n                        cnt = (cnt + go(A, *y, seen, m) * go(A, z, seen, m) % MOD) % MOD;\n                    }\n                }\n                m.insert(x.clone(), cnt);\n            }\n            *m.get(&x).unwrap()\n        }\n        let mut t = 0 as i64;\n        for x in &A {\n            t = (t + go(&A, *x, &seen, &mut m)) % (1e9 as i64 + 7);\n        }\n        return t as i32;\n    }\n}\n```\n\n3. **T**urn the top-down solution upside-down to create the bottom-up solution\n```\n// TODO: implement me!\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 LL = long long;\n    using VI = vector<int>;\n    using Set = unordered_set<int>;\n    using fun = function<LL(int)>;\n    int numFactoredBinaryTrees(VI& A, LL MOD = 1e9 + 7, LL t = 0) {\n        Set seen{ A.begin(), A.end() };\n        fun go = [&](auto x) {\n            auto cnt = 1LL;\n            for (auto y: A) {\n                if (x % y)\n                    continue;\n                auto z = x / y;\n                if (seen.find(z) != seen.end())\n                    cnt = (cnt + (go(y) * go(z) % MOD) % MOD);\n            }\n            return cnt;\n        };\n        for (auto x: A)\n            t = (t + go(x)) % MOD;\n        return t;\n    }\n};\n```\n\n2. **R**emember each subproblem\'s optimal solution via a DP memo\n```\nclass Solution {\npublic:\n    using LL = long long;\n    using VI = vector<int>;\n    using Set = unordered_set<int>;\n    using fun = function<LL(int)>;\n    using Map = unordered_map<int, LL>;\n    int numFactoredBinaryTrees(VI& A, LL MOD = 1e9 + 7, Map m = {}, LL t = 0) {\n        Set seen{ A.begin(), A.end() };\n        fun go = [&](auto x) {\n            if (m.find(x) == m.end()) {\n                auto cnt = 1LL;\n                for (auto y: A) {\n                    if (x % y)\n                        continue;\n                    auto z = x / y;\n                    if (seen.find(z) != seen.end())\n                        cnt = (cnt + (go(y) * go(z) % MOD) % MOD);\n                }\n                m[x] = cnt;\n            }\n            return m[x];\n        };\n        for (auto x: A)\n            t = (t + go(x)) % MOD;\n        return t;\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 LL = long long;\n    using VI = vector<int>;\n    using Set = unordered_set<int>;\n    using fun = function<LL(int)>;\n    using Map = unordered_map<int, LL>;\n    int numFactoredBinaryTrees(VI& A, LL MOD = 1e9 + 7, Map m = {}, LL t = 0) {\n        Set seen{ A.begin(), A.end() };\n        sort(A.begin(), A.end());\n        for (auto x: A)\n            m[x] = 1LL;\n        for (auto x: A) {\n            for (auto y: A) {\n                if (x % y)\n                    continue;\n                auto z = x / y;\n                if (seen.find(z) != seen.end())\n                    m[x] = (m[x] + (m[y] * m[z] % MOD) % MOD);\n            }\n        }\n        for (auto [_, cnt]: m)\n            t = (t + cnt) % MOD;\n        return t;\n    }\n};\n```
[]