leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0650.cpp (874B)


1 // DP
2 class Solution {
3 static int dp[1001][1001];
5 int minSteps(const int n, int total, int clip) const {
6 if (total == n) return 0;
7 if (total > n) return 1000000;
8 if (total + clip > n) return 1000000;
9 if (dp[total][clip] != -1) return dp[total][clip];
10 return dp[total][clip] = min(1 + minSteps(n, total + clip, clip), 2 + minSteps(n, total * 2, total));
11 }
13 public:
14 Solution() { memset(dp, 0xFF, sizeof(dp)); }
15 int minSteps(const int n) const { return n == 1 ? 0 : 1 + minSteps(n, 1, 1); }
16 };
18 int Solution::dp[1001][1001];
20 // Math
21 class Solution {
22 public:
23 int minSteps(int n) const {
24 int res = 0, crnt = 2;
25 while (n > 1) {
26 while (n % crnt == 0) {
27 res += crnt;
28 n /= crnt;
29 }
30 crnt++;
31 }
32 return res;
33 }
34 };