问题描述
给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
解决方案
解决本题要用到的是动态规划，同时要先知道什么是丑数，题目也很明确的说明了丑数是什么，接下来就是实现在代码方面找到丑数，对于找丑数可以使用python的一次循环遍历就可以得到需要的丑数，因为只存在2,3,5这三个元素，遍历过程中不会太复杂；知道了如何判断丑数后就是进一步的丑数的变形方式，本题所使用的动态规划并不是太复杂的动态规划，这里要用到的新的变量“指针”（p2,p3,p5）此处pi是可以与i相乘的最小丑数的位置，设置了三个指针后从最小的开始，指针的移动表示在从大到小的寻找丑数，nums[i]是由三个指针乘以相应的数得到的，把相对应的pi + 1表示没有乘过次nums的最小丑数变大了，然后一个数一个数的加进数组中，直到遍历结束。
具体代码如下：
n = int(input()) nums = [1]#放入第一个丑数1 p2 = 0# 三个初始化指针 p3 = 0 p5 = 0 for i in range(1, n):# 遍历n得到所有丑数 ushu = min(nums[p2] * 2, nums[p3] * 3, nums[p5] * 5)# 从小到大，按照丑数定义收集丑数 nums.append(ushu)# 将丑数放进结果数组中 if(nums[i] == nums[p2] * 2): p2 += 1# 指针移动，从小到大地寻找丑数 if(nums[i] == nums[p3] * 3): p3 += 1 if(nums[i] == nums[p5] * 5): p5 += 1 print(nums[n-1]) # 返回第n个丑数 |
运行效果：
结语
虽然是使用了动态规划的方式解决了本题，但对与动态规划还是处于模糊状态，还是会继续学习关于动态规划的知识，尽快熟悉并掌握运用，同时，做本题是要有一个清晰的思路，先得到什么，然后再做一步怎么样的操作。
