Recursively compute the minimum operators for both options and take the minimum.
Use memoization to cache results for each target.
The cost for using x^k is k if k > 0 (since xx...*x needs k multiplications), otherwise 2 (for division).
Code

[{"language":"C++","code":"class Solution {\npublic:\n    unordered_map<int, int> memo;\n    int x;\n    int leastOpsExpressTarget(int X, int target) {\n        x = X;\n        return dfs(target);\n    }\n    int dfs(int t) {\n        if (t == 0) return 0;\n        if (t < x) return min(2 * t - 1, 2 * (x - t));\n        if (memo.count(t)) return memo[t];\n        int k = 0, p = 1;\n        while (p * x <= t) {\n            p *= x;\n            ++k;\n        }\n        int left = dfs(t - p) + k;\n        int right = dfs(p * x - t) + k + 1;\n        return memo[t] = min(left, right);\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    unordered_map</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> memo;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> x;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> leastOpsExpressTarget</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> X</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> target</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        x </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> X;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        return</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(target);</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    }</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> t</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        if</span><span style=\"color:#242
Related Tags
