题目描述
给你一个整数 n
,请你找出并返回第 n
个 丑数 。
丑数 就是质因子只包含 2
、3
和 5
的正整数。
思路
动态规划。因为丑数只是包含质因数 2
、3
和/或 5
的正整数,因此我们可以使用三个指针从头遍历丑数数组。这三个指针分别是 2、3 和 5 的整数指针,记作 p2, p3, p5
。每次计算第 n 个丑数时可以得出如下动归方程:
dp[n]=min(dp[p2]∗2,dp[p3]∗3,dp[p5]∗5)
之后比较 dp[n]
与这三个比较值,相等的话给对应指针加一,代表着已经越过了当前最小值,下一次比较的是稍大的值。
想得太多