为了打发时间想了一个递回解
# call poss(7, 4, 0) in main()
def poss(field, pick, cur_max):
if field < pick:
return 0
if pick == 0:
return cur_max ** field
if field == 0:
return 0
_sum = 0
i = cur_max if cur_max > 0 else 1
for n in range(i, 10):
_sum += poss(field-1, pick-1, n)
_sum += i * poss(field-1, pick, cur_max)
return _sum
第一个参数是剩余字段数
第二个参数还有几个字段要满足条件
第三个就是当前最大值
其中如果满足的位数已经取完且还有剩余位，
例如 1234*** 剩下三位各可以取0~3，
可以直接算所以就列入base case
general case 的话这里不好说明，
自己在纸笔上展开可能比较好理解，
原则上就是分为目前最高位是否要取大于等于目前最大值。
例如 poss(3, 1, 5)
意思是目前剩3位,还有1位要满足不小于5,
可以展开成目前最大位要满足, 有5~9,
所以后面就是poss(2, 0, 5) ~ poss(2, 0, 9)
还有目前最大位不要满足, 有0~4,
所以后面就是 5组 (0~4) poss(2, 1, 5)
而当前最大值是0的话比较特别，
想了很久一开始也完全想不到如何把它凑进递回式里
我自己的电脑可以跑在0.008秒内
不过我如果是在短时间限制的面试里大概也只写得出brute force XD