JZ49 丑数

题目描述：

JZ49 丑数

丑数：把只包含质因子2、3和5的数称作丑数（Ugly Number）

• 递推属性：丑数只包含质因子2、3、5，因此有“丑数=某较小丑数 x 某质因子” 如：10 = 5 * 2

思路：动态规划

DP:

• 状态表示：dp[i]
  • 集合：表示第 i 个丑数
  • 属性：数值
• 状态计算：f[i] = min(f[a]*2，f[b]*3, f[c]*5) ---- 问题是：如何确定a、b、c的下标

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
      	// 特殊边界 = 0
        if (index == 0) return 0;
      	// 记录 *2 *3 *5 的上一个数的下标
        int a = 0, b = 0, c = 0;
        int f[index];
        // 初始化
        f[0] = 1;
        for (int i = 1; i < index; ++i) {
            int n2 = f[a] * 2, n3 = f[b] * 3, n5 = f[c] * 5;
            f[i] = min(min(n2, n3), n5);
          	// 此时，需要更新abc的值
          	// 判断依据是，是否和当前的f[i]相等，如相等则说明当前范围已经超过f[*]x2,3,5
          	// 需要更新，以找到最小的满足 f[*]x2,3,5 大于f[i-1]
            if (f[i] == n2) a++;
            if (f[i] == n3) b++;
            if (f[i] == n5) c++;
        }
        return f[index-1];    
    }
};