hot插件 wordpress/seo培训中心

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  

1 是丑数。
n 不超过1690。

思路

根据动态规划五部曲:

1)dp[i]表示第 i 大的丑数

2)递推公式:我们有dp[i],那么dp[i+1]可以由dp[p1]*2,dp[p2]*3,dp[p3]*5,p1,p2,p3分别指向不同的指针,因为我们需要存储当前的最小的下一个丑数,如果dp[i+1]==dp[p1]*2 or dp[p2]*3 or dp[p3]*5.

那么p1++ or p2++ or p3++

3)递推顺序:从前到后,确定了dp[i],再推导dp[i+1],但是dp[i+1]并不是由dp[i]推导的!

4)初始化:我们初始化dp[1]=1,表示第一大的丑数为1

5)手动模拟--略

注意事项:有些数字(eg:6)可以由dp[3]*2,推导,也可以由dp[2]*3推导,那么到底是哪个指针加加操作呢?

积相等的指针(p1,p2,p3)都应该进行加加操作!

代码

#include<vector>
using namespace std;class Solution {
public:int nthUglyNumber(int n) {vector<int> dp(1691);          //设置状态:dp[i]表示第i大的丑数dp[0] = 1;      //可以不加这句话dp[1] = 1;int p1 = 1;int p2 = 1;int p3 = 1;for (int i = 2; i <= n; ++i) {dp[i] = min(dp[p1] * 2, min(dp[p2] * 3, dp[p3] * 5));if (dp[i] == dp[p1] * 2) ++p1;else if (dp[i] == dp[p2] * 3) ++p2;else if (dp[i] == dp[p3] * 5) ++p3;}return dp[n+1];}
};

 

小结

有些题目dp[i]并不是由dp[i-1]推导的,而是根据具体问题具体分析,比如本题的dp[i]就是由之前的某一个dp[j]*2 or dp[q]*3 or dp[m]*5   ,那么我们就需要设置三个指针分别指向同一个起始位置.根据相等与否,进行相应操作.