leetcode两数相加：leetcode902go最大为N的数字组合
leetcode两数相加：leetcode902go最大为N的数字组合解释：我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，示例 2：输入：D = ["1" "4" "9"] N = 1000000000 输出：29523示例 1：输入：D = ["1" "3" "5" "7"] N = 100 输出：20解释：可写出的 20 个数字是：1 3 5 7 11 13 15 17 31 33 35 37 51 53 55 57 71 73 75 77.
题目我们有一组排序的数字 D，它是 {'1' '2' '3' '4' '5' '6' '7' '8' '9'} 的非空子集。（请注意，'0' 不包括在内。）
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。
例如 D = {'1' '3' '5'}，我们可以写出像 '13' '551' '1351315' 这样的数字。
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
示例 1：输入：D = ["1" "3" "5" "7"] N = 100 输出：20
解释：可写出的 20 个数字是：
1 3 5 7 11 13 15 17 31 33 35 37 51 53 55 57 71 73 75 77.
示例 2：输入：D = ["1" "4" "9"] N = 1000000000 输出：29523
解释：我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。
提示：D 是按排序顺序的数字 '1'-'9' 的子集。
1 <= N <= 10^9
解题思路分析1、动态规划-数位dp；时间复杂度O(log(n))，空间复杂度O(log(n))
func atMostNGivenDigitSet(digits []string n int) int {
str := fmt.Sprintf("%d" n)
m := len(digits)
k := len(str)
dp := make([]int k 1) // dp[i] 表示 长度为i的N（最后i位）的个数
dp[0] = 1
// 1、考虑k位数的可能
for i := 1; i <= k; i {
value := str[k-i] - '0'
for j := 0; j < len(digits); j {
v := digits[j][0] - '0'
if v < value { // 小于，剩下i-1位随便用： m^(i-1)
dp[i] = dp[i] int(math.Pow(float64(m) float64(i-1)))
} else if v == value { // 等于：考虑i-1位
dp[i] = dp[i] dp[i-1]
}
}
}
// 2、考虑非k位数的可能
for i := 1; i < k; i {
dp[k] = dp[k] int(math.Pow(float64(m) float64(i))) // m^i
}
return dp[k]
}总结
Hard题目，数位dp题目
