由简单题入手动态规划、递归、特定算法情景优化思路23见解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了由简单题入手动态规划、递归、特定算法情景优化思路23见解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3468字，纯文字阅读大概需要5分钟。
内容图文
leetcode刷题-650题，只有两个键的键盘
题目描述：
最初在一个记事本上只有一个字符 ‘A‘。你每次可以对这个记事本进行两种操作：
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A‘。输出能够打印出 n 个 ‘A‘ 的最少操作次数。
示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 ‘A‘。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA‘。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA‘。
说明: n 的取值范围是 [1, 1000] 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/2-keys-keyboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
博主看到这个题的个人思路：
最优解，下意识的往动态规划方向思考，并且根据题目特性得出：“在此题中，我们必然会经历一次复制，并且必然存在一种解，是由n次A的粘贴操作组成”。所以，生硬的想一下dp[n] = min(a,b)。
动态方程推演：
初始格子为一个n长的int数组，此题不存在n=0的情况，从1开始，所以这个数组长度+1
int[] dp = new int[n+1];
dp[i]即储存当n=i时，此时所需要的最小次数。即答案的解。
当n=1时：dp[1]=0; （读题，最初即为‘A‘，不需要任何操作就可以满足条件，so，这里是一个)
if (n=1) {
return 0;
}
当n=2时：dp[2]=2;（复制一次，粘贴一次，后面此类将不再赘述）
...
此时发现，数字的特性：当数字可以被某个数整除时（如：9%3 == 0），那么，我们会发现，9/3=3，我们复制3份3个‘A‘，即可达到目的。但是，这个解是最优解吗？
操作次数为：
复制->粘贴->粘贴->复制->粘贴->粘贴
‘A‘->‘AA‘->‘AAA‘->‘AAA‘->‘AAAAAA‘->‘AAAAAAAAA‘
步骤6
思考一下在题目限制内，我们都有哪些操作方式：
题目要求最小次数，假如，我一次粘贴之后，9变成8，此时8可以由2个4达成。
模拟这个操作，发现不可以。
那继续想想其它情景
...
此时，突然意识到算法。数学理论、数学公式、数学概念。这些算法题，何其像当初的数学应用题啊...
这个操作，难道花里胡哨描述半天，就是数学里的最大因子求解吗？（真的是吗？）
理一下思路：
验证真理的方式，实践出真知——穷举
（Ps.越来越像解应用题了...公式或者概念记不清了就开始穷举推导...伟人都给了现成的了）
当我要求得20的最优解时，并且我的达成方式只能是复制粘贴。
那么，
1.从1开始粘贴20次，result=21
2.从1到2，然后10次，result=13
3.从1到2，从2到4？？，从4开始5次，
4.从1到2，从2到3，从3到4，从4到5，{然后从5开始4次||从5到10 【从5到10？？？】}，从10到20）
...
此时发现，最优解里我们需要其它最优解支持，
也就是说，当我们在情况3时，我们需要2到4的最优解；在情况4时，我们需要在{}中的最优解，在这里还需要【】中的最优解
这时候会不会觉得乱？其实不是，我们只需要“假设我们已经获得最优解”即可。
通过规律，我们可以较粗略的看出，随着大因子的引入，次数在慢慢下降的，
而且，我们的大因子可以帮助我们尽快的达成数值增长，而我们付出的则是达到它的代价+1次复制操作
此时带入数学思维，同时回想起，这种默认子条件为最优的“递归思想”复杂度。
也就是说，最差的情况也不过是退化掉变成持平与原方法。即4这种。
所以，我们有理由认为，最大的因子数就是我们需要的最优解
此时变化思路，开始尝试：
// 最大因子求解方法，最大，那就从一半开始向前搜索吧
// 若没有则返回1，原因是题目中必须要有结果，那么最差的值不过是其本身，也就是除数为1的时候
public int findMaxFactors(int k) {
int res = 1;
for (int i = k/2; i>=2; --i) {
if (k % i == 0) {
res = i;
break;
}
}
return res;
}
有了这个最大的因子数之后，开始思考怎么使用
求n=20为例子思考：
20的最大因子数为10，如果知道达到n=10的最小值，那么在此基础上->复制->粘贴
10的最大因子数为5，如果直到到达n=5的最小值，那么在此基础上->复制->粘贴
5的最大因子数是...5是质数，我们只能通过复制->粘贴->粘贴->粘贴->粘贴来到达，那么也就是说，其自身
以上述思路：
int count = 0; // 弄个计数器统计记录结果
while() {
int mf = findMaxFactors(n);
count += n/mf;
}
/** 此时还差个循环结束条件
* 通过上述发现，当最后的数开始变成质数的时候，也就是结束出结果的时候，即mf=1的时候
*/
int pre = n; // 记录上一个数
int count = 0;
int mf = 0;
while(pre != 1) {
mf = findMaxFactors(pre);
count += pre/mf;
pre = mf;
}
至此，去试试吧。
class Solution {
public int minSteps(int n) {
if (n == 1) {
return 0;
}
int pre = n;
int count = 0;
int mf = 0;
while(pre != 1) {
mf = findMaxFactors(pre);
count += pre/mf;
pre = mf;
}
return count;
}
// 寻找n的最大因子数
public int findMaxFactors(int k) {
int res = 1;
for (int i = k/2; i>=2; --i) {
if (k % i == 0) {
res = i;
break;
}
}
return res;
}
}
结果：
这个结果很满意了。
分析一下时间复杂度和空间复杂度吧。
同时，这道题也可以熟悉一下递归与动态规划。
递归：
class Solution {
public int minSteps(int n) {
// 递归解法
if (n == 1) {
return 0;
}
int res = n; // 质数情况
// 合数情况处理
for (int i = 2; i < n; i++) {
if (n%i == 0) {
res = Math.min(res, minSteps(i)+n/i);
}
}
return res;
}
}
运行结果：
动态规划：
class Solution {
public int minSteps(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, n);
dp[1] = 0;
for (int i=2; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
if (i%j == 0) {
dp[i] = Math.min(dp[i], dp[j]+i/j);
}
}
}
return dp[n];
}
}
运行结果：
这两种解法思路如果有需要在留言吧，我想以后遇到典型些的，或者说有意义些的相关题目在总结，于此题，就当是玩玩吧。
并且感觉这递归的结果有些不正常...重复值的话，不该如此效率啊。
原文：https://www.cnblogs.com/boziyouning/p/14678779.html
内容总结
以上是互联网集市为您收集整理的由简单题入手动态规划、递归、特定算法情景优化思路23见解全部内容，希望文章能够帮你解决由简单题入手动态规划、递归、特定算法情景优化思路23见解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。