JAVA DFS +DPsolution beat 99.9% 4ms with details explanation

  • 0
     public int nthUglyNumber(int n) {
                int[] dp=new int[n];dp[0]=1;
                return DFS(dp,1,0,0,0,n);
        private int DFS(int[] dp, int i, int p2, int p3, int p5, int n) {
            if (i==n)return dp[n-1];
            dp[i]=Math.min(dp[p2]*2, Math.min(dp[p3]*3,dp[p5]*5));
            if (dp[i]==dp[p2]*2)p2++;
            if (dp[i]==dp[p5]*5)p5++;
            return DFS(dp, i+1, p2, p3, p5, n);

    we can get a tree like this which contains all the ugly number ;just use three point to dfs because of I can not find the relationship between three point ; so we can think it just like this picture
    each point 3 and 5 can have the 23and 25;35 child.and we can use a tricky in programming that if we meet 23=6 we should p2++;p3++;if 3*5:p5++;p3++;just like the code writ in DFS function

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.