[数据结构与算法][M数学] lc650. 只有两个键的键盘(dp+思维+质因数)

1. 题目来源

链接：650. 只有两个键的键盘

2. 题目解析

十分好的一道题目啊。数学的 $O(\sqrt{n})$ 解法，和 dp 的 $O(n)$ 解法都很不错。

方法一：数学+质因数分解

• 考虑，$n=x_1?x_2?...?x_k$，我们可视为 $x_1$ 是先复制一次，然后粘贴 $x_1?1$ 次，那么现在的总长度就是：原有的一个 A 加上 $x_1?1$ 个 A，也就是共 x_1 个 A，即 x_1 即为总长度。
• 而针对 x_2，我们也可视为是先将现有总长度复制一次，然后在后面粘贴 $x_2?1$次，那么总长度就是 $x_1+x_1(x_2?1)$ 即为 $x_1?x_2$。
• 同理可得，$n=x_1?x_2?...?x_k$ 只要将 $n$ 分解为 $x_i\ge 2$正整数的乘积，就能一一对应一种方案。 乘以数字 1 是没有意义的。而数字之和就是操作次数。
• 再考虑，当乘数中有合数出现时，合数一定可以因式分解。即 $x=p?q,x\ge 2，p,q>1$，我们仅需证明 $p+q\le x$ 即可证明任意合数都可以进行分解，那么最后必然是所有的质数的乘积构成 $n$。即答案(操作次数)即为 $n$ 的所有质因子分解式的和。
• 考虑，$(p?1)?(q?1)>1$，因为 $p,q>1$，那么 $(p?1)?(q?1)=p?q?p?q+1=x?p?q+1>1$，那么 $x>p+q$ 恒成立。
• 这就说明了 $n=x_1?x_2?...?x_k$ 不存在合数，即全为质数。那么由整数唯一分解定理可得 $n$ 有唯一质因数分解式，累加和即为答案。

方法二：dp

• 贪心怕是不行，那就 dp 呗。
• 状态定义： f[i] 表示得到 i 个字符 A 所需的最小操作次数。初始化 f[1]=0。答案 f[n]。
• 状态转移：每次考虑最后一个位置是从哪转移过来的。 可以明确的是，多次 copy 情况下，我们只需要枚举 i 的所有约数 j 即可。即 f[i]=f[j]+i/j 意味着 i/j 次中，经历一次复制 f[j] 个，i/j -1 次拷贝到达状态 i。和数学解法的思路大致一样。同理，也可以 f[i]=f[i/j]+j，经历一次复制 f[i/j] 个，拷贝 j-1 次到达状态 i。
• 状态转移剪枝：
  • 在枚举 i 的约数时，显然只需要枚举到根号 i
  • 也可以枚举 i 的时候只考虑 n%i==0的所有的 i 情况即可。但是这个想法比较抽象，不推荐。也懒得去想证明了。

当然这种选不选问题，可以 dfs，但没必要。

• 时间复杂度：$O(\sqrt{n})$
• 空间复杂度：$O(1)$

dp

class Solution {
public:
    int minSteps(int n) {
        vector<int> f(n + 1, 1e9);
        f[1] = 0;
        for (int i = 2; i <= n; i ++ ) {
            // if (n % i == 0)      // 加上优化效率，剪枝。
            for (int j = 1; j <= i / j; j ++ ) {
                if (i % j == 0) {
                    f[i] = min(f[i], f[j] + i / j);
                    f[i] = min(f[i], f[i / j] + j);
                }
            }
        }

        return f[n];
    }
};

数学

class Solution {
public:
    int minSteps(int n) {
        int res = 0;
        for (int i = 2; i <= n / i; i ++ ) {
            if (n % i == 0) {
                int t = 0;
                while (n % i == 0) n /= i, t ++ ;
                res += i * t;
            }
        }
        if (n > 1) res += n;

        return res;
    }
};