LeetCode 650. 两个键的键盘

Categories:

题目描述
思路分析
1. 解法一：质因数分解（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 650. 两个键的键盘

思路分析

解法一：质因数分解（推荐）

核心思路：

每次操作只有两种：Copy All（复制全部）或 Paste（粘贴）

若要得到 n 个 ‘A’，最优策略是找到 n 的质因数分解：n = p1 × p2 × … × pk

对每个质因子 p，需要 1 次 Copy All + (p-1) 次 Paste，共 p 步

因此总操作次数 = n 所有质因子之和

复杂度分析：

时间复杂度：O(√n)，对 n 进行质因数分解

空间复杂度：O(1)，仅使用常数额外空间

class Solution {
    public int minSteps(int n) {
        int ans = 0;

        // 对 n 进行质因数分解，累加所有质因子
        for (int d = 2; d * d <= n; d++) {
            while (n % d == 0) {
                ans += d;
                n /= d;
            }
        }

        // 若 n 还有大于 1 的质因子
        if (n > 1) {
            ans += n;
        }

        return ans;
    }
}

func minSteps(n int) int {
    ans := 0

    // 对 n 进行质因数分解，累加所有质因子
    for d := 2; d*d <= n; d++ {
        for n%d == 0 {
            ans += d
            n /= d
        }
    }

    // 若 n 还有大于 1 的质因子
    if n > 1 {
        ans += n
    }

    return ans
}

解法二：动态规划

核心思路：

定义 dp[i] 为屏幕上显示 i 个 ‘A’ 所需的最少操作次数

对每个 i，枚举其因子 j（j 为上一次 Copy All 时的数量）

若 i % j == 0，则 dp[i] = min(dp[i], dp[j] + i/j)，其中 i/j 表示粘贴次数加1次复制

复杂度分析：

时间复杂度：O(n√n)，对每个 i 枚举因子

空间复杂度：O(n)，dp 数组

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];

        // 初始化为较大值
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
        }

        for (int i = 2; i <= n; i++) {
            // 枚举因子 j，j 为上一次 Copy All 的数量
            for (int j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    // 从 j 个复制一次再粘贴 (i/j - 1) 次
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                    // 从 i/j 个复制一次再粘贴 (j - 1) 次
                    dp[i] = Math.min(dp[i], dp[i / j] + j);
                }
            }
        }

        return dp[n];
    }
}

func minSteps(n int) int {
    dp := make([]int, n+1)

    // 初始化为较大值
    for i := 2; i <= n; i++ {
        dp[i] = i
    }

    for i := 2; i <= n; i++ {
        // 枚举因子 j，j 为上一次 Copy All 的数量
        for j := 1; j*j <= i; j++ {
            if i%j == 0 {
                // 从 j 个复制一次再粘贴 (i/j - 1) 次
                if dp[j]+i/j < dp[i] {
                    dp[i] = dp[j] + i/j
                }
                // 从 i/j 个复制一次再粘贴 (j - 1) 次
                if dp[i/j]+j < dp[i] {
                    dp[i] = dp[i/j] + j
                }
            }
        }
    }

    return dp[n]
}

相似题目

题目	难度	考察点
279. 完全平方数	中等	动态规划/数学
343. 整数拆分	中等	动态规划/数学
991. 坏了的计算器	中等	贪心/数学
263. 丑数	简单	质因数分解
264. 丑数 II	中等	动态规划/堆
1250. 检查「好数组」	困难	数论/质因数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/80262493