题解 | #丑数#

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param index int整型
 * @return int整型
 */
func GetUglyNumber_Solution(index int) int {
	// write code here
    if index<1{
        return 0
    }
	dp := make([]int, index+1)
	dp[1] = 1
	m2 := 1
	m3 := 1
	m5 := 1
	for i := 2; i <= index; i++ {
		for j := m2; j < i; j++ {
			if dp[j]*2 > dp[i-1] {
				m2 = j
				break
			}
		}
		for j := m3; j < i; j++ {
			if dp[j]*3 > dp[i-1] {
				m3 = j
				break
			}
		}
		for j := m5; j < i; j++ {
			if dp[j]*5 > dp[i-1] {
				m5 = j
				break
			}
		}
		next := min(dp[m5]*5, dp[m3]*3, dp[m2]*2)
		dp[i] = next
	}


	return dp[index]
}
func min(num1, num2, num3 int) int {
	less := num1
	if num2 < less {
		less = num2
	}
	if num3 < less {
		less = num3
	}
	return less
}

动态规划