LeetCode650 只有两个键的键盘

发表于 | 分类于 |
字数统计: 342 | 阅读时长 ≈ 1

链接：https://leetcode-cn.com/problems/2-keys-keyboard/description/

题面

给定一个字母 A，已知你可以每次选择复制全部字符，或者粘贴之前复制的字符，求最少需要几次操作可以把字符串延展到指定长度。

解法

一道之前做过的动规题了
虽然是过了 但是后来发现有点小问题
记录一下正确的写法
dp[i]表示延展到长度i的最少操作次数
对于每个位置j, 如果j可以被i整除, 那么i就可以由长度j操作得到
其操作次数等价于把一个长度为1的A延展到长度i/j
然后这个操作只需要做一次，意味着只要找到一个因子更新dp值就可以跳出循环
原因是这以延展步骤是等价的
18 1->2->18(1->9) 1->3->18(1->6) 次数是相同的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSteps(int n) {
        // dp[i]表示延伸到长度i的最少操作次数
        vector<int> dp(n + 1);
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j < sqrt(i) + 1; j++) {
                if (i % j == 0) {
                    dp[i] = min(dp[i], dp[j] + dp[i / j]);
                    break;
                }
            }
            cout << dp[i] << ' ';
        }
        return dp[n];
    }
};

dp的代码总是这么简短->_->