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