当前位置: 首页 > >

力扣 264. 丑数 II dp

发布时间:

https://leetcode-cn.com/problems/ugly-number-ii/

思路:




d



p


i




dp_i


dpi?表示第i个丑数的值,显然它是一个单调递增的数组,用




i


d



x


1






i


d



x


2






i


d



x


3




idx_1、idx_2、idx_3


idx1?、idx2?、idx3?记录按照




?


2





?


3





?


5



*2、*3、*5


?2、?3、?5方式扩展的上个丑数的下标,显然




d



p


i




dp_i


dpi?要取最小的那个值。


class Solution {
public:
int nthUglyNumber(int n) {
vector dp(n+1);
dp[1]=1;
int idx1=1,idx2=1,idx3=1;
for(int i=2;i<=n;i++)
{
dp[i]=min({dp[idx1]*2,dp[idx2]*3,dp[idx3]*5});
if(dp[i]==dp[idx1]*2)
++idx1;
if(dp[i]==dp[idx2]*3)
++idx2;
if(dp[i]==dp[idx3]*5)
++idx3;
}
return dp[n];
}
};



友情链接: