Leetcode daily

The problem statement was pretty simple,
Intially you a letter A written on the Notepad.
you can either of these 2 operations, however many times.

copy all the contents of the notepad (partial copy is not allowed)
paste the content from your copy at any location in the text.

I solved this problem using DP.
which looks very similer in implementation to sieve's algorithm to finding the prime.

here's my solution.

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+3, INT_MAX);
        dp[1] = 0;
        for (int i = 2; i<= n;i++) {
            if (i % 2==0) { 
                dp[i] = min(dp[i], dp[i/2]+2);
            } else { 
                dp[i] = min(dp[i], i);
                for (int j = 2 * i ,times = 2; j <= n; j+=i, times++) { 
                    dp[j] = min(dp[j], dp[i] + times); 
                }
            }
        }
        return dp[n];
    }
};

Blog

pastaPicaso

Join Our Newsletter. No Spam, Only the good stuff.

Related