LeetCode刷题【剑指 Offer 49】丑数

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

dp,算是dp吧

解题思路

此处撰写解题思路

代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int[] numArr = new int[]{2,3,5};
        int[] pArr = new int[3];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(dp[pArr[0]]*numArr[0],dp[pArr[1]]*numArr[1]),dp[pArr[2]]*numArr[2]);
            for (int p = 0; p < pArr.length; p++) {
                if (dp[i] == dp[pArr[p]]*numArr[p]){
                    pArr[p]++;
                }
            }
        }
        return dp[n-1];
    }
}