【LeetCode】650. 只有两个键的键盘
650. 只有两个键的键盘（中等）
-
思路
- 不同于以往通过加减实现的动态规划，这里需要乘除法计算位置。因为粘贴操作是倍数增加，使一个一维数组 dp，其中位置 i 表示延展到长度 i 的最少操作次数。
- 对于每个位置 j ，如果 j 可以被 i 整除，那么长度 i 就可以由长度 j 得到，其操作次数等价于把一个长度为 1 的 A 延展到长度为 i/j ，因此递推公式为：
dp[i] = dp[j] + dp[i/j];。比如 i = 10 ，可以在 i=5 的时候，选择复制全部字符并粘贴，就扩展为 10 个 A。
-
代码
class Solution { public: int minSteps(int n) { vector<int> dp(n+1, 0); for(int i=2; i<=n; ++i){ dp[i] = i; for(int j=2; j*j<=i; ++j){ if(i % j == 0){ dp[i] = dp[j] + dp[i/j]; break; } } } return dp[n]; } }; -
收获
- 理解起来有点难，自己跟着代码算一下比较好理解。
- 我自己模拟的时候，计算错了，忘记复制全部字符，而我每次复制的字符都是之前复制的两倍（即 2 - 4 - 8 - …）。