扔棋子问题

丢棋子问题

http://www.nowcoder.com/questionTerminal/d1418aaa147a4cb394c3c3efc4302266

Python解
转载一下写的比较好的一个博客https://www.cnblogs.com/willwuss/p/12256475.html
简单说以下自己看懂的三种方法
1.暴力递归（不建议）
设函数F(n,k)返回的是给定n,k所返回的最小试验次数。
Case1:当n=0时，根据已知不用实验即可得到结果，故F(0,k)=0
Case2:当k=1且n>0时，实际上就是示例1的情况，从第一层开始尝试，最差情况一直到最后一层故F(n,k)=n,n>0。
Case3:对于一般化情况进行分析，第一个棋子是从第i层扔的，此时会有两种情况：
1.棋子碎了，总数量-1变成k-1，并且从第i层下面开始搜索，F(i,k) = F(i-1,k-1);
2.棋子没碎，总数量仍为k，从第i层上面开始扔，F(n-i,k)
为了得到最差情况，我们应该选两者中较大的情况即max{F(i-1,k-1),F(n-i,k)}+1，+1表示在第i层扔了一次，由于i的取值为[1,n]，因此F(n,k) = min{max{F(i-1,k-1),F(n-i,k)} ( $1$ )}+1。(不建议使用第三个样例在Pycharm中会崩溃) 时间复杂度为O(n!)

class Solution:
    def solve(self,n ,k ):
        if n<1&nbs***bsp;k<1:
            return 0
        return self.helper(n,k)

    def helper(self,n,k):
        if n==0:return 0
        if k==1:return n
        mins = 0x7fffffff

        for i in range(1,n):
            mins = min(mins,max(self.helper(i-1,k-1),self.helper(n-i,k)))

        return mins+1

2.动态规划
在上述过程中，不难发现整个过程中的各个情况实际上是存在递推式的，我们不妨建立矩阵dp，维数为{n+1,k+1}，矩阵中的每个元素dp[i][j]都表示F(i,j)。初始位置正如1中所分析的Case1和Case2，我们用n=3,k=2为例，初始条件，tbd表示待定

$图片说明$
对于其余位置，我们建立递推式即dp[n][k] = min{max{dp[i-1][k-1],dp[n-i][k]}+1

class Solution1:
    def solve(self , n , k ):
        # write code here
        if n<1&nbs***bsp;k<1:
            return 0
        if k==1:
            return n
        dp = [[0]*(k+1) for i in range(n+1)]
        for i in range(1,n+1):
            dp[i][1] = i
        for i in range(1,k+1):
            dp[1][i] = 1

        for i in range(2,n+1):
            for j in range(2,k+1):
                mins = 0x7fffffff
                for m in range(1,i+1):
                    mins = min(mins,max(dp[m-1][j-1],dp[i-m][j]))
                dp[i][j] = mins+1
        return dp

3.最优解法
最优解比一上各种方法都快。首先我们换个角度来看这个问题，以上各种方法解决问题是N层楼有K个棋子最少仍多少次。现在反过来看K个棋子如果可以仍M次，最多可以解决多少楼层这个问题。根据上文实现的函数可以生成下表。在这个表中记作map， map[i][j]的意义为i个棋子仍j次最多搞定的楼层数.
通过研究map表发现，第一排的值从左到有一次为1，2，3...，第一纵列都为0，初次之外的其他位置(i, j),都有 map[i][j] == map[i][j-1] + map[i-1][j-1] + 1.
将设i个棋子仍j次最多搞定m层楼，“搞定最多”说明每次仍的位置都是最优的且在棋子肯定够用的情况下，若第1个棋子仍在a层楼是最优的。

如果第1个棋子以碎，那么就向下，看i-1个棋子扔j-1次最多搞定多少层楼；
如果第1个棋子没碎，那么就向上，看i个棋子扔j-1次最多搞定多少层楼；
a层楼本身也是被搞定的1层；
1、2、3的总楼数就是i个棋子扔j次最多搞定的楼数，map表的生成过程极为简单，同时数值增长的极快。原始问题可以通过map表得到很好的解决。
例如，想求5个棋子搞定200层楼最少扔多少次的问题，注意到第5行第8列对应的值为218，是第5行的所有值中第一次超过200的值，则可以知道5个棋子搞定200层楼最少扔8次。同时在map表中其实9列10列的值也完全可以不需要计算，因为算到第8列就已经搞定，那么时间复杂度得到进一步的优化。另外还有一个特别重要的优化，我们知道N层楼完全用二分的方式扔logN+1次就直接可以确定哪层楼是会碎的最低层楼，所以当棋子数大于logN+1时，我们就可以返回logN+1.
如果棋子数位K，楼数位N, 最终的结果位M次，那么最优解的时间复杂度为O(KxM), 在棋子数大于logN+1时，时间复杂度为O(logN). 在只要1个棋子的时候， KxM等于N, 在其他情况下 KxM要比N得多
```
import math
class Solution:
 def solve(self , n , k ):
     if n<1&nbs***bsp;k<1:
         return 0
     if k==1:
         return n
     bsTimes = math.log2(n)+1

     if k>bsTimes:return bsTimes

     dp = [0]*k
     res = 0
     while True:
         res = res+1
         previous = 0
         for i in range(len(dp)):
             tmp = dp[i]
             dp[i] = dp[i]+previous+1
             previous = tmp
             if (dp[i]>=n):
                 return res
```