leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0650.cpp (874B)

0 1 // DP 2 class Solution { 3 static int dp[1001][1001]; 4 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 } 12 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 }; 17 18 int Solution::dp[1001][1001]; 19 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 };