运行要求运行时间限制：2sec内存限制：1024MB取款，规定每人只能取以下金额一次：1元和6元，6X6=36元，6X6X6=216元和9元，9X9=81元，9X9X9=729元请问，如果你想从银行取N元，应该取多少次取钱？规定取出的钱不能再次存入银行。输入前提1<=N<=100000N为整数输入。输入是按照以下标准从命令行输入N输出提取N元所需的最少提取次数x例1输入127输出41元、9元、36元（=6X6）元、81元（=9X9），经过以上4次提取，一共可以提取127元例2输入3输出31元，1元，1元，经过以上3次提取，总共可以提取3元例3输入44852输出16看题可以看做是一个整数N，应该被1分割，小于N的6次方，小于N的9次方。求分割次数最少的情况。解题思路1、把每种情况都统计一遍，然后计算最小值，显然是不可能的。因为N的最大值是100,000，所以统计每种类型会花费很长时间。2、每一个整数I都有一个对应的值X，X是用于提取I的钱的最少提取次数。例如I为1，则X=1（1次重复取出1）例如I为2，则X=2（2次重复取1）例如I为3，则X=3（3次重复取出1）比如我是4，那么X=4（重复取出1，重复4次）例如，如果我是5，那么X=5（取出1，重复6次）例如，如果我是6，那么X=1（取出6一次）比如我是7，那么X=2（取出6，再取出1）当我是7的时候，有2种取出方式,1.一种是取出1，然后处理剩下的6个数2.一种是取出6，然后处理body下的1。第一种方法所需的数量为1（取出1需要1次）+1（取出6至少需要1次）=2次。需要的方法次数为1（需要一次取出6）+1（至少需要一次取出1）=2次，所以当i为7时，最后的结果为min（第一种方法,第二种方法)=2当我为8时,有两种方法1.一种是取出1,然后处理剩下的7.2.一种是取出6,然后处理剩下的2.第一种方法要求数量为1（取出1需要1次）+2（取出7至少需要2次）=3次方法二需要的数量为6（取出1需要1次）6)+2(至少需要2次才能取出2)=3次所以当我是8的时候，最后的结果是min(第一种方法，第二种方法)=3当我是9的时候，有3种方法1.一种是取出1，然后处理剩下的8个2.一种是取出6，然后处理剩下的3个3.一种是取出9，然后处理剩下的0个需要的个数第一种方法是1（需要1次取出1)+ 3（最少3次得到8）=4次第二种方法需要的次数为1（1次得到6）+ 3（最少3次得到3）=4次第三种方法所需数量为1（一次取出9个）+ 0（最少0次取出0个）=4次，所以当i为9时，最终结果为min（第一种方法，第二种1方法，第三种方法)=1当我为10时，有3种方法1.一种是取出1，然后处理剩下的92.一种是取出6，然后处理剩下的42.一种是取出9，再处理剩下的1。第一种方法需要的个数为1（取出1需要1次）+ 1（至少需要1timetotakeout9)=2次第二种方法该方法需要的次数为1（需要1次才能得到6）+4（最少需要4次才能得到4）==5次该方法需要的次数第三种方法是1（需要1次获得9）+ 1（取出1至少需要1次）=2次，所以当i为9时，最后的结果min（第一种方法，第二种方法，第三种方法）=2即可隐约觉得可以用递归的方法来解决问题，因为对于整数N，第一步的split方法可以过滤掉。例如对于整数37，第一步去掉1，最少需要的次数是在A的第一步去掉6的情况下，最少需要的次数是第一步去掉36的情况B的，最少需要的次数是在C的第一步去掉9的情况下，最少需要的次数是D，然后求出A，B，C，D的最小值用a函数求N的最小取款次数。第1步去掉6的倍数，或者9的倍数，或者1，剩下的数的最小取款可以再次应用。这个功能。另一种方式是从1遍历到N，对每个整数求最小的方法。对于1-5的整数i，最小解就是i本身。对于i=6和i=9，最小解为1。首先，将已知信息存储在一个数组memo中。其他整数可以根据前面的索引i-1、i-6、i-9等数组值来计算，最后找到memo最后一项的值。这道题的方法也可以参考我之前写的一个爬楼梯的解法。AtCoderContextABC126CTypicalStairs（经典楼梯）代码方法1importsyssys.setrecursionlimit(20000000)N=int(input())memo=[-1foriinrange(110000)]defcalculate(n):ifn==0:memo[n]=0return0ifmemo[n]!=-1:returnmemo[n]res=npow6Num=1whilepow6Num*6<=n:pow6Num=pow6Num*6res=min(res,计算(n-pow6Num)+1)pow9Num=1whilepow9Num*9<=n:pow9Num=pow9Num*9res=min(res,calculate(n-pow9Num)+1)memo[n]=int(res)returnint(res)result=calculate(N)print(memo[N])方法2N=int(input())defcalculate(n):memo=[0foriinrange(N+1)]#0-Nforindexinrange(1,n+1):pow6=6pow9=9ifindex<6:memo[index]=indexelifindex==6:memo[index]=1elifindex==9:memo[index]=1else:values=[]whilepow6<=index:values。append(1+memo[index-pow6])pow6=pow6*6whilepow9<=index:values.append(1+memo[index-pow9])pow9=pow9*9values.append(1+memo[index-1])minValue=min(values)memo[index]=minValuereturnmemoresult=calculate(N)print(result[N])总结一下这个问题有很多解决方法，我会在后续文章中介绍其他的解决方法。目前最常用的解决方法是使用动态规划的思想来求解。部分文章发布在微信个人订阅号，欢迎关注
