力扣AC：丑数II - 动态规划

题目链接

丑数II

题目描述

实现代码

动态规划思想：记dp[i]表示第i个丑数，因为每个位置的丑数跟2,3,5三个数相关，是仅仅由这三个质因数组成的数，写出前十个丑数可以看出，从1开始之后，每个位置的丑数的值都是2,3,5其中一个与前面的某个丑数相乘的结果，因此可以定义三个指针p1/p2/p3分别对应2,3,5相乘的位置，则状态转移方程为:

dp[i] = min(2dp[p1], 3dp[p2], 5*dp[p3])

p1，p2，p3更新条件：min选择到对应的位置；
更新方式：自增1

实现代码：

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        int p1 = 1;
        int p2 = 1;
        int p3 = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++) {
            dp[i] = Math.min(Math.min(2*dp[p1], 3*dp[p2]), 5*dp[p3]);
            p1 += (dp[i] == 2*dp[p1] ? 1: 0);
            p2 += (dp[i] == 3*dp[p2] ? 1: 0);
            p3 += (dp[i] == 5*dp[p3] ? 1: 0);
        }
        return dp[n];
    }
}