剑指offer-33-丑数

思路

dp[i]=min(dp[i-某个值]2，dp[i-某个值]3，dp[i-某个值]*5)
这是动态规划寻找状态方程的思路
本题不能这么做，所以要从000出发，用三个指针标记 某个值
注意 1算是第一个丑数

代码

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

        }   
        return dp[index-1];
    }
}