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


  • 0
    T
     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[p3]*3)p3++;
            if (dp[i]==dp[p5]*5)p5++;
            return DFS(dp, i+1, p2, p3, p5, n);
        }
    

    0_1478597152551_upload-e4c0fa79-dce4-4242-b252-c54022122934
    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
    0_1478597386722_upload-a6aa995c-989b-4dc0-b48c-0800c247f5d7
    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.