📃题目
给你一个整数 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 通常被视为丑数。
提示：
- 1 ⇐ n ⇐ 1690
🤔思路
本题属于动态规划系列，按照动态规划五部曲来分解题目
1、确定dp数组以及下标含义
本题求解的是第n个丑数，因此定义一维数组保存每个丑数
其中dp[i]表示第i+1个丑数，最终返回的结果应为dp[n-1]
2、确定递推公式
除了第一个丑数以外，每一个丑数都是由前面的丑数乘以2、3、5得到的
那么存在两个问题：前面的丑数是指哪个，乘以2还是乘以3还是乘以5
对于前面丑数的选择上，使用三个指针进行跟踪，这三个丑数分别乘以2、乘以3、乘以5，最后选取其中最小值
dp[i] = min(dp[p2]*2,min(dp[p3],dp[p5]));指针会随之更新，继续向后选择丑数
if(dp[i]==dp[p2]*2) p2++;
if(dp[i]==dp[p3]*3) p3++;
if(dp[i]==dp[p5]*5) p5++;上述代码可能会感到疑惑，为什么要判断三次，而不是一次，应该用if-else啊
这是因为部分丑数存在多种组合，比如6是32和23得到的
如果只更新p2的话，下一次计算丑数时会再次选择6，产生了重复，所以需要将p3也进行更新
3、dp数组如何初始化
dp数组从第一个数字开始进行迭代，dp[0] = 1
对于三个指针的初始值也是从第一个开始，p2=p3=p5=0
4、确定遍历顺序
dp[i]的计算依赖前面的丑数选择，因此遍历顺序应从前往后
5、举例推导dp数组
// i=1，p2=0,p3=0,p5=0
dp[1]=min(1*2,1*3,1*5)=2
// i=2, p2=1,p3=0,p5=0
dp[2]=min(2*2,1*3,1*5)=3
// i=3, p2=1,p3=1,p5=0
dp[3]=min(2*2,2*3,1*5)=4
// i=4, p2=2,p3=1,p5=0
dp[4]=min(3*2,2*3,1*5)=5
// i=5, p2=2,p3=1,p5=1
dp[5]=min(3*2,2*3,2*5)=6
// i=6, p2=3,p3=2,p5=1（这里的p2和p3同时更新很重要，否则dp[6]=6）
dp[6]=min(4*2,3*3,2*5)=8可以对照推导过程去理解递推公式的意思，在输出结果不对时也可以进行查缺补漏
通过上述的动规五部曲的分析，实际C++代码如下：
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n,1);
int p2=0,p3=0,p5=0;
for(int i=1;i<n;i++){
dp[i] = min(dp[p2]*2,min(dp[p3]*3,dp[p5]*5));
if(dp[i]==dp[p2]*2) p2++;
if(dp[i]==dp[p3]*3) p3++;
if(dp[i]==dp[p5]*5) p5++;
}
return dp[n-1];
}
};🔚总结
本文最关键的地方在于当前丑数与前面丑数之间的联系，以及前面丑数的选择陷阱，与往常动规题目的递推公式相比，有一点绕，但是最终的递推公式还是相当简洁。