每日一题_650. 只有两个键的键盘

每日一题_650. 只有两个键的键盘

leetcode

题目:
每日一题_650. 只有两个键的键盘
题意分析:
题目的意思是说,初始情况下只有一个A的情况下,如何能够得到n个A,其中能用的操作只有复制和粘贴,并且粘贴只能粘贴最近一次copy的内容。

动态规划:
首先,我们可以先尝试一些较小的数,体会一下其中的规律,我尝试了一下11以内,然后首先发现所有的素数的操作次数都是自身的n,然后比如8,我们只需要在有4个A的时候,复制一下再粘贴,那么就能得到8个A,为了方便我们的描述,我们设dp[i]表示得到i个A所需要的操作次数,那么 d p [ 8 ] = d p [ 4 ] + 2 dp[8] = dp[4] + 2 dp[8]=dp[4]+2,8是偶数,我们再看9,我们在得到3个A的时候,复制一次,再粘贴两次就得到了9个A,即 d p [ 9 ] = d p [ 3 ] + 3 dp[9] = dp[3] + 3 dp[9]=dp[3]+3,从这里,我们其实就可以窥出一些端倪了,首先得到 i 个A和得到j(j < i)个A有关,也就是说具有最优子结构,因此使用动态规划。但是j的选取我们并不知道,但是必须满足能整除i,即 i % j = 0。在这个的前提下,取选择最小的一个,因此算法如下:

dp[i]表示得到i个A需要的最小的操作次数,状态转移方程:
f [ i ] = min ⁡ j ∣ i ( f [ j ] + i j ) f[i] = \min\limits_{j|i} ( f[j] + \frac{i}{j} ) f[i]=j∣imin​(f[j]+ji​)

代码:

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[1] = 0;

        for (int i = 2; i <= n; i ++)
            for (int j = 1; j < i; j ++)
                if ( i % j == 0)
                    dp[i] = min(dp[i], dp[j] + i/j);

        return dp[n];
    }
};




数学:
从第一个方法的转移方程中,我们得到n个A,实际上我们是把j个A重复复制了i/j遍,也就是 n = j * (n / j),虽然这么写相当于废话,但仔细看转移方程: d p [ n ] = d p [ j ] + n / j dp[n] = dp[j] + n/j dp[n]=dp[j]+n/j,因此实际上我们把n进行了质因数分解,因为递归求解j也是这么做的,因此我们来换个思路,刚刚从n往回看,我们从头开始看:

如果我们将 1 次 Copy All + x 次 Paste 看做一次“动作”的话。
那么一次“动作”所产生的效果就是将原来的字符串变为原来的 x + 1 x + 1 x+1倍。
最终的得到n个A的最小操作次数方案可以等价以下操作流程:

  1. 起始对长度为 1 的记事本字符进行 1 次 C o p y A l l + k 1 − 1 Copy All + k_1 - 1 CopyAll+k1​−1次 Paste 操作(消耗次数为 k 1 k_1 k1​,得到长度为 k 1 k_1 k1​的记事本长度);
  2. 对长度为为 k 1 k_1 k1​ 的记事本字符进行 1 次 C o p y A l l + k 2 − 1 Copy All + k_2 - 1 CopyAll+k2​−1 次 Paste 操作(消耗次数为 k 1 + k 2 k_1 + k_2 k1​+k2​ ,得到长度为 k 1 ∗ k 2 k_1 * k_2 k1​∗k2​的记事本长度)
    … …

最终经过 k 次“动作”之后,得到长度为 n 个A,即有:
n = k 1 ∗ k 2 ∗ k 3 ∗ . . . ∗ k x n = k_1 *k_2 *k_3 *... * k_x n=k1​∗k2​∗k3​∗...∗kx​
因此问题转化为,
K = ∑ k i K = \sum k_i K=∑ki​
求 K K K的最小值。
对于 k i k_i ki​而言 ,如果是一个合数,那么 k i = a ∗ b k_i = a * b ki​=a∗b,很容易证明
a ∗ b > a + b ( a > 1 , b > 1 ) a * b > a + b \quad(a > 1, b > 1) a∗b>a+b(a>1,b>1)
因此 K K K 要取得最小,只需要对 k i k_i ki​ 不断分解,直至不能分解,也就是素数了,这也就是为什么我们一开始尝试看出来的质数的操作次数都是自身n。
因此问题转化为对n进行质因数分解,然后将所有的质因数求和就行了。

代码:

class Solution {
public:
    int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i * i <= n; i ++)
            while (n % i == 0)
            {
                ans += i;
                n /= i;
            }

        if (n != 1) ans += n;

        return ans;
    }
};
上一篇:排序算法


下一篇:DataWorks控制台升级