算法问题——丢棋子的动态规划问题

https://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266?tpId=117&&tqId=35279&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

解答问题：https://www.cnblogs.com/willwuss/p/12256475.html

题目描述

  一座大楼一共有0~N层，地面算第0层，最高一层为第N层。已知棋子从第0层掉落肯定不会摔碎，从第i层掉落可能回摔碎，也可能不会摔碎(1<=i<=N)。给定整数N作为楼层数，再给定整数K作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下仍的最少次数。一次只能仍一个棋子。

例子

N=10, K=1. 返回10。因为只有1颗棋子，所以不得不从第一层开始一直试到第十层，最差情况要扔10次。

N=3, K=2. 返回2。现在第2层仍1颗棋子，如果碎了，试第1层；如果没碎，试第3层。

N=105, K=2. 返回14。

 第一颗棋子尝试层数若第一颗碎了第二颗棋子尝试的层数第一次尝试141~13第一次没碎2715~26第二次没碎3928~38第三次没碎5040~49第四次没碎6051~59第五次没碎6961~68第六次没碎7770~76第七次没碎8478~83第八次没碎9085~89第九次没碎9591~94第十次没碎9996~98第十一次没碎102100,101第十二次没碎104103第十三次没碎105 

 方法一：暴力算法

设P(N,K)的返回值时N层楼时有K个棋子在最差的情况下仍的最少次数。

如果N==0，棋子在第0层肯定不会碎，所以P(0, K) = 0;如果K==1，楼层有N层，只有1个棋子，故只能从第一次开始尝试，P(N,1)=N;对于N>0且K>1, 我们需考虑第1个棋子是从那层开始仍的。如果第1个棋子从第i层开始仍，那么有以下两种情况:   (1) 碎了。没必要尝试第i层以上的楼层了，接下来的问题就变成了剩下i-1层楼和K-1个棋子，所以总步数为 1+P(i-1, K-1);   (2)没碎。 那么可以知道没必要尝试第i层及其以下的楼层了，接下来的问题就变成了还剩下N-i层和K个棋子，所以总步数为 1+P(N-i, K).根据题意应该选取(1)和(2)中较差的那种情况，即 max{ P(i-1, K-1), P(N-i, K)}+1。 由于i的取值范围是 1到N, 那么步数最少的情况为， P(N, K)=min{ max{P(i-1, K-1), P(N-i, K)}(1<=i<=N) }+1。 public int solutionOne(int N, int K){ if ( N<1 || K<1 ) return 0; return helper1(N, K); } private int helper1(int N, int K){ if ( N==0 ) return 0; if ( K==1 ) return N; int min = Integer.MAX_VALUE; for(int i=1; i<=N; ++i){ min = Math.min(min, Math.max( helper1(i-1, K-1), helper1(N-i, K))); } return min+1; }

方法二：动态规划

  通过研究以上递归函数发现， P(N, K)过程依赖于P(0...N-1, K-1) 和 P(0...N-1, K)。所以，若把所有的递归的返回值看作是一个二维数组，可以用动态规划的方法优化递归过程。从而减少计算量。   dp[0][K] = 0, dp[N][1] = N, dp[N][K] = min( max(dp[i-1][K-1], dp[N-i][K])) + 1。

public int solutionTwo(int N, int K){ if ( N<1 || K<1 ) return 0; if ( K == 1 ) return N; int[][] dp = new int[N+1][K+1]; for(int i=1; i<dp.length; ++i) { dp[i][1] = i; } for(int i=1; i<dp.length; ++i) { for(int j=2; j<=K; ++j) { int min = Integer.MAX_VALUE; for(int k=1; k<i+1; ++k) { min = Math.min(min, Math.max(dp[k-1][j-1], dp[i-k][j])); } dp[i][j] = min + 1; } } return dp[N][K]; }

方法五： 最优解

最优解比一上各种方法都快。首先我们换个角度来看这个问题，以上各种方法解决问题是N层楼有K个棋子最少仍多少次。现在反过来看K个棋子如果可以仍M次，最多可以解决多少楼层这个问题。根据上文实现的函数可以生成下表。在这个表中记作map， map[i][j]的意义为i个棋子仍j次最多搞定的楼层数。

棋子数\次数01234567891010123456789102013610152128364555301371425416392129175401371530569816225538550137153162119218381 

通过研究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. 如果第1个棋子以碎，那么就向下，看i-1个棋子扔j-1次最多搞定多少层楼；   2. 如果第1个棋子没碎，那么就向上，看i个棋子扔j-1次最多搞定多少层楼；   3. 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得多。

public int solutionFive(int N, int K) { if (N < 1 || K < 1) return 0; int bsTimes = log2N(N) + 1; if (K >= bsTimes) { return bsTimes; } int[] dp = new int[K]; int res = 0; while (true) { ++res; int previous = 0; for (int i = 0; i < dp.length; ++i) { int tmp = dp[i]; dp[i] = dp[i] + previous + 1; previous = tmp; if (dp[i] >= N) { return res; } } } } private int log2N(int N) { return (int) (Math.log(N) / Math.log(2)); }