题解 | #放苹果，python递推方式#

放苹果

http://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf

递推的方式，利用公式f(m, n)=f(m, n-1)+f(m-n, n)来填表。
将m个苹果放入n个盘子里，包含了2个事件：至少有一个盘子空着的事件A，和所有盘子都不空的事件B（每个盘子都至少有一个苹果）。A∪B即所有情况。A就是求f(m, n-1)，B就是f(m-n, n)。事件B表示每个盘子都有一个苹果时再放m-n个苹果，等价于每个盘子都没有苹果时放m-n个苹果，所以可以直接写成 f(m-n, n)。注意m-n可能为负数，此时要返回0。

例如，f(4,4)=f(4,3)+f(0,4)，f(0,4)等于1，表示在4个盘子中各放1个苹果

while True:
    try:
        m, n = map(int, input().split())
    except:
        break
    else:
        a = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(m+1):
            for j in range(1,n+1):
                if i == 0 or i== 1 or j == 1:
                    a[i][j] = 1
                elif i-j >= 0:
                    a[i][j] = a[i][j-1] + a[i-j][j]
                else:
                    a[i][j] = a[i][j-1]
        print(a[m][n])

全部评论

推荐最新楼层

11-25 19:33

南京理工大学 C++

C++选手秋招总结

秋招进行到现在终于能写总结了。完全没想到战线会拉这么长，过程会如此狼狈，不过更应该怪自己太菜了。好在所有的运气都用在了最后，也是有个去处。背景：双2本硕科班，无竞赛，本科一段研究所实习，硕士一段大厂暑期实习但无转正。技术栈是C++ & Golang，实习是客户端音视频（而且是鸿蒙端开发），简历两个C++项目一个Golang项目。主要投递岗位：后端，cpp软开，游戏服务端，测开，以及一些不拘泥于Java的岗位。从8月起总共投递123家公司，笔试数不清了，约面大约30家。offer/oc/意向：友塔游戏（第一个offer，面试体验很好，就是给钱好少南瑞继保（计算机科班点击就送（限男生），不...

乡土丁真真：佬很厉害，羡慕~虽然我还没有到校招的时候，也想讲一下自己的看法：我觉得不是CPP的问题，佬的背书双2，技术栈加了GO，有两段实习。投了123，面了30.拿到11个offer。这个数据已经很耀眼了。这不也是CPP带来的吗？当然也不止是CPP。至少来说在这个方向努力过的也会有好的结果和选择。同等学历和项目选java就会有更好的吗？我个人持疑问态度。当然CPP在方向选择上确实让人头大，但是我觉得能上岸，至于最后做什么方向，在我看来并不重要。至于CPP特殊，有岗位方向的随机性，java不是不挑方向，只是没得选而已。也希望自己以后校招的时候能offer满满