算法的基本思想分析面试题

    有同学和我讲了一个这样的面试题目，你站在一个一百层的高楼上，每层楼都有自己的突出板子（相互不遮挡），你有两个弹弹球（材质完全一样），但是你不知道它最多能承受多少层楼的重力加速度后碎裂，如果没碎裂你可以准确的接住这丢下去的弹球（假设你是个高手）。现在要你用最少的测试次数来测试弹弹球最多能丢到第几层楼。
    一看到这个题，我们程序员第一反应当然是分治减治法，一般求最小，最少啊。估计没人会想要用穷举法吧（当然迫不得已也是有的）。好确定分治减治之后，一般定式会想到折半法，原因很简单，折半够利索。但是一想折半球不够啊，log2（100）可是比2大很多啊！！思路稍微混乱的人就怒了，nnd2个球要爷想什么办法啊！不过够冷静的人会想，怎么着比一个好吧，两个球如果折半至少节约50次了。（最倒霉的情况是弹弹球最多能丢到49层楼，第一个丢在50碎了，然后悲剧的穷举）在想想没碎是可以弹起来的呀，都已经把100分两段了，为什么不分小点，这样穷举也不用费劲啊。好就分4段看看行不，先把第一个球丢第25层，没碎继续，这样实验最多3次后知道是那段了，在穷举最多也就3+23次（第75层碎了，穷举）。既然这样不如再分小点，分10段好了，显然次数又在减少，然而什么时候最适合呢。有同学说在接近最好的时候都算下就出来了，显然这不是我们程序员应该有的思想，我们的想法是--好编程解决。
    然而问题又出来了，你如何设置你的编程思路呢，又或者题目发生变化是n层大楼你有r个玻璃球呢？这都是我们程序员需要解决的问题。
    假设在n层楼上对第r层抛一次(对应方程中的"+1")，会有两种情况发生：
    (1)玻璃球碎，说明在第1到第r层楼中必有一层为临界层，问题转化为一个子问题：求F(r,k-1)
    (2)玻璃球不碎，说明临界层在第r+1层到第n层这n-r层楼中，问题转化为子问题:求F(n-r,k)
    因为考虑的是最坏情况下抛球策略的所需测试次数的最小值，所以取这两种情况中的较大值，并遍历每一个可能的r，取其情况的最小值即得到F(n,k)。
    这样你发现--嘿嘿原来是一个动态规划的问题。我们知道动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
    而动态规划最重要的是找到子问题和原问题建立的关系公式和边界。
    设F(n,k)为用k个玻璃球来测试n层大厦的临界层的最少次数，状态转移方程如下：
    F(n,k)=min{max{F(r,k-1), F(n-r,k)}+1, 1<=r<=n}
    边界条件:F(n,1)=n-1, F(1,k)=F(0,k)=0
    至此万事俱备只欠东风。接下来我们来看程序，以前实现过现在就偷懒在网上找个现成的了。

 #include <iostream>
 #include <fstream>
 #include <sstream>
 #include <string>
 #include <cmath>
 #include <iomanip>
 #include <vector>
 #include <deque>
 #include <list>
 #include <queue>
 #include <stack>
 #include <map>
 #include <algorithm>
 #include <limits>
 #include <utility>
 #include <ctime>
 #include <bitset>
 using namespace std;
 
 #define MAX_FLOOR 512
 #define MAX_BALL  100
 
 int dp(int n, int k)
 {
     if(k<1 || n<1) return -1;    //错误输入
 
     if(k==1) return n-1;        //去掉一些trivial case
     if(n==1) return 0;
 
     int M[MAX_BALL][MAX_FLOOR];
     int i,j,r;
     int temp, min;
 
     for(i=0;i<=k;i++) M[i][0]=M[i][1]=0;    //F(1,k)=F(0,k)=0
     for(j=2;j<=n;j++) M[1][j]=j-1;            //F(n,1)=n-1
 
     /*
     状态转移方程：
     F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}
     */
     for(i=2;i<=k;i++)
         for(j=2;j<=n;j++)
         {
             min = numeric_limits<int>::max();
             for(r=1;r<=j;r++)
             {
                 temp = max(M[i-1][r], M[i][j-r])+1;
                 if(temp<min)
                     min = temp;
             }
             M[i][j] = min;
         }
 
     return M[k][n];//F(n,k)
 }
 
 int main()
 {
     int n,k;
     
     cin>>n>>k;
     cout<<dp(n, k)<<endl;
     
     return 0;
}

好运行下得出input: 100 2  output: 14
也许你会很神奇，这怎么得到的，好我们看具体数据：
第一个小球预计投下的楼层数为[14,27,39,50,60,69,77,84,90,95,99].
第二个小球需要测试的次数就为[13,12,11,10,9,8,7,6,5,4].
程序解决出来的方案是不是相当nice。
在换一种思考方式：
此问题关键是找到算法的公式，假设最坏情况需要n次，则归纳后得到：
在第一个小球不损害的情况下，第一次：n层，第二次：n+（n-1）层，依次类推到第n-1次：n+（n-1）+...+（n-（n-1）），由此，问题简化为：
1+2+3+...+n，在n大于多少时大于楼层数，得到结果为14。
其实有时候我们会发现，暴力方法是相当可爱的，有很多时候我们解决不了的时候，我们可以用暴力慢慢尝试，优秀的方法会慢慢浮出水面的。就像上面的动态规划问题，到了只有1个球的时候，唯一可行的就是暴力法，然而他却提供给我们一种局部策略。我们只要想到尽可能的少做暴力也就是编程之美咯。（一方浅见，大家勿喷！）
（第二次博客，不对请指教，建议请跟帖，谢谢！！！）