Python | 动态规划解决“返回第n个丑数”

问题描述给你一个整数 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]#放入第一个丑数1p2 = 0# 三个初始化指针p3 = 0p5 = 0for 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 += 1if(nums[i] == nums[p5] * 5): p5 += 1print(nums[n-1])  # 返回第n个丑数运行效果：

结语虽然是使用了动态规划的方式解决了本题，但对与动态规划还是处于模糊状态，还是会继续学习关于动态规划的知识，尽快熟悉并掌握运用，同时，做本题是要有一个清晰的思路，先得到什么，然后再做一步怎么样的操作。实习编辑：李欣容稿件来源：深度学习与文旅应用实验室（DLETA）