本文共 1027 字,大约阅读时间需要 3 分钟。
Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.
Example 1:
Input: 3Output: 3Explanation:Intitally, we have one character 'A'.In step 1, we use Copy All operation.In step 2, we use Paste operation to get 'AA'.In step 3, we use Paste operation to get 'AAA'.
Note:
The n will be in the range [1, 1000].思路:如果知道了 i 的结果,那么2 * i的步骤只需在 i的结果上加上2即可,一次复制,一次粘贴。同理3 * i的结果为一次复制,2次粘贴;
int minSteps(int n) { vector dp(n + 1, INT_MAX); dp[1] = 0; for (int i = 1; i <= n; i++){ int k = 2; for (int j = i * 2; j <= n; j += i){ dp[j] = min(dp[j], dp[i] + k); k++; } } return dp[n];}
转载地址:http://txxei.baihongyu.com/