2 Keys Keyboard

題目描述

解題思路

題目大意自不必說，至于說解法，這道題目有想過往動态規劃方面去想，但想着想着就被可愛的某婷帶偏了，不過最後還竟另辟蹊徑，通過對數字本身的研究而解出本題。大緻思路如下：

對于n個字元A，如果想要找出最小的複制粘貼步數，為何不從它的因數找起呢？以42為例，42=21*2=7*3*2，也就是說我要先複制初始的一個A，粘貼得到一個A之後，再複制這兩個A，粘貼2次得到6個A，再複制這6個A，粘貼6次就可以得到42個A啦，當然關于這理論的證明我暫時無法給出，不過Accept證明我這個想法是ok的。

C++代碼實作

class Solution {
public:
    int minSteps(int n) {
        int t = ;
        int a[], p = -;;
        while (n != ) {
            while (n % t != ) {
                t++;
            }
            a[++p] = t;
            n = n / t;
        }
        int result = ;
        for (int i = ; i <= p; ++i) {
            result += a[i];
        }
        return result;
    }
};
           

運作結果顯示

動态規劃解法

後來又檢視了題目解析，重新構思動态規劃的方法後發現有異曲同工之妙，即令dp[i]表示要想生成i個字元所需要的步數，初始值dp[0]=dp[1]=0;狀态轉移方程為dp[i]=min(dp[i],dp[j]+i/j),i>1,j<i且i%j==0;因為如果i是j的倍數，那麼i可以通過粘貼i/j-1次得到，但還要加上一次指派這j個字元，是以就是dp[j]+i/j.
           

實作代碼如下：

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+,);

        dp[] = dp[] = ;

        for(int i=;i<n+;++i){
            for(int j=;j<i;++j){
                if(i%j==){
                    dp[i] = min(dp[i], dp[j]+i/j);
                }
            }
        }
        return dp[n];
    }
};