起首说说笔者写这道题的履历吧,不怕大家笑话,这道题我足足写了3小时...最开始看到这道题的时间我想的是我可以将 n 从前的使用 A 的次数以次数为键用 Hashmap 存起来,然后碰到 n 的时间直接去 Hashmap 内里拿,当我去提交的时间,发现有些测试用例是过不了的,比若说741。然后我重新思考,发现可以用递归,但是由于思考深度不敷,又有一些情况没思量到,去提交的又数次失败...真的恼火。
由于递归从最开始就没思量到那种情况,因此改起来特殊贫苦,而这不得不使我重新选择一条路出发。以是由此看来啊,做题之前真要静下心来思考,思考范围要广一点。
接下来就说第一种方法,我称之为数学规律法。
1.数学规律法
class Solution { public int minSteps(int n) { int result = 0; int i; //当 n 被分解到 1 时,退出循环 while(n != 1){ for( i = 2; i <= n; i++){ //遍历找出能整除 n 的 i if(n % i == 0){ n /= i; //result加上能整除 n 的 i result += i; i = 2;//乐成整除 n 后,举行新的 i 循环,找出下一个能整除 n 的i } } } return result; }}2.动态规划(LeetCode官方题解)
1.动态规划本领
先简朴说说动态规划的一些本领吧。
确定好dp数组的寄义,肯定要明确dp所表现的是什么
动态规划的数据通常是由前面一个数据推导演变而来的,因此必要得出推导公式
末了就是dp数组的初始化了,这个必要额外留意,由于初始化一旦有问题,就会导致终极答案堕落
2.思绪
举个例子,照旧拿 12 来说吧,12 = 1 -> 2 -> 3 -> 6 -> 12,我们会发现要得出 12 的最小使用次数,必要知道 6 的最小使用次数再加上复制粘贴的次数(2次),进而必要知道 3 的最小使用次数再加上复制粘贴的次数(2次)...总的来说就是如果要找出 i 个 A ,则肯定要先找到 i 的因数 j ,而后通过 i / j 次复制粘贴得到 i 个 A 因此会发现这个递推规律:
此中, j | i 表现 j 能整除 i ,i / j 表现复制粘贴的次数。对于每一个 f 只必要便是最小的 f[j] + i / j。
class Solution { public int minSteps(int n) { int[] f = new int[n + 1]; for (int i = 2; i <= n; ++i) { f = Integer.MAX_VALUE; for (int j = 1; j <= i; ++j) { if (i % j == 0) { f = Math.min(f, f[j] + i / j); } } } return f[n]; }}