Python|动态规划与回溯求数字个数
问题描述
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
动态规划思考及解决
读完该问题，会想到动态规划+排列组合来决解，因为是求的不同数字的个数，所以要将每一个满足的值加起来，故采用动态规划是很方便的。
第一步：创建一个dp数组，记录下n=0-2的个数(dp=[1,10,91])；
第二步：判断n>=3,满足进行遍历3-n，利用排列组合计算出不同的数字个数；
第三步：将满足的个数加上前一个的个数并放入dp数组中，最后返回dp数组的最后一个值。
代码:
#动态规划
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
dp=[1,10,91]
if n>=3:
for i in range(3,n+1):
s,k,g=9,9,0 #s为排列组合所求i值不同数字的个数
while g<i-1:
s=s*k
k-=1
g+=1
dp.append(s+dp[-1])
return dp[-1]
else:
return dp[n]回溯思考及解决
当然该题也能用递归来进行解答，回溯算法则更加的简洁，不需要设很多的未知数。
第一步：创建一个递归函数，将一个空字符串res与字符串l=’1234567890’，传入该函数中；在构造函数中创建一个self.num=0来记录个数；
第二步：遍历字符串l，并进行函数递归操作，将取到的字符从l中取出；
第三步：设置递归终止条件，且执行一次递归self.num+=1，最终返回self.num。
代码：
#递归解决：
class Solution:
def __init__(self):
self.num=0
def countNumbersWithUniqueDigits(self, n: int) -> int:
def A(res,l):
if res:
if int(res)>=10**n:#终止条件
return
if res[0]==str(0):#第一位不能为0
return
self.num+=1
for i in l:
A(res+i,l.replace(i,''))
A('','1234567890')
return self.num参考文献
本文主要是讲了从动态规划+排列组合来解答该题，和回溯算法解答该题的思路以及代码，当然两种方法都可，虽然回溯算法易理解且简洁，但算法时间复杂度过高。
END
主 编 | 王文星
责 编 | 王卓越
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读