微软的扔杯子问题-动态规划

Contents

1. 1. 题目描述
2. 2. 不等式解法
3. 3. 动态规划解法

题目描述

一种杯子，若在第N层被摔破，则在任何比N高的楼层均会破，若在第M层不破，则在任何比M低的楼层均不会破，给你两个这样的杯子，让你在100层高的楼层中测试，要求用最少的测试次数找出恰巧会使杯子破碎的楼层。

不等式解法

所有讨论基于2个杯子的情况：
下图中所有图示的红线均表示剩下两个杯子的时候的试摔位置，当杯子破碎后，也就是只剩下一个杯子的时候，只需要从已知范围的最底层向已知范围的最高层逐层试摔。

• 当只有一层的时候，需要一次试摔。
• 当有两层的时候，需要两次试摔。
• 当需要三层时候，首先讨论是否可以通过两次试摔完成，可以发现可以，方法如图。
• 当需要四层时候，首先讨论是否可以通过两次试摔完成，可以发现已经不行，因此至少需要三次试摔。
• 当需要五层时候，首先讨论是否可以通过小于等于三次试摔完成，如果不行则讨论最多四次试摔的情况。依次类推，如下图：

因此，当有100层的时候，最多需要n次试摔，使得

$$ {n+(n-1)+(n-2)+…+1 >= 100} \tag{1} $$

然后对n上取整，因此n=14。最差情况需要14次试摔。

** 试摔方法为：第一次在14层扔，如果没破，在27层(14+13)继续扔，不破在39层(27+12)继续扔，依次类推。 如果破了，剩下一个杯子，从已知范围的最底层向已知范围的最高层逐层试摔。**

动态规划解法

假设用dp[i][j]表示剩余i层，j个杯子时候最少需要多少次试摔。

• （1）dp[i][1] = i，也就是说当只剩下一个杯子时，只能从第一层开始逐层向上试摔。
• （2）dp[0][j] = 0，当只剩下0层时，只需要进行0次试摔。
• （3）dp[1][j] = 1，当只剩下1层时，只需要进行1次试摔，前提是j>0
• （4）dp[i][j] = min(1=<k<i)(max(dp[k-1][j-1], dp[j-k][j]) + 1)
  ，也就是当杯子破和不破的时候分成两个子问题，分别求解，之后求子问题试摔次数的最大和作为这种分解方法的试摔次数，之后取这些所有分拆子问题的方法中，使子问题和最小的方法。

可以记录route[i][j]，表示剩下i层j个杯子时，下一次试摔的楼层。当j=1时，从这个范围内的最底层依次向最高层试摔。

//dp.c  
#include <stdio.h>  
#define LAYER 101  
#define CUP 3  
int main(){  
    int dp[LAYER][CUP], route[LAYER][CUP], i, j, k;  
    for(i=1; i<LAYER; i++){  
        dp[i][1] = i;   
        dp[i][0] = 0;  
    }  
    for(i=1; i<CUP; i++){   
        dp[1][i] = 1;  
        route[1][i] = 0;  
        dp[0][i] = 0;  
    }   
    for(i=2; i<CUP; i++)  
        for(j=2; j<LAYER; j++){  
            dp[j][i] = j;  
            route[j][i] = 0;  
            for(k=1; k<j; k++){  
                int min = dp[k-1][i-1] > dp[j-k][i]? dp[k-1][i-1]+1: dp[j-k][i]+1;  
                route[j][i] = min <= dp[j][i]? k: route[j][i];  
                dp[j][i] = min < dp[j][i]? min: dp[j][i];  
            }  
        }  
    printf("MIN STEP IS %d\n", dp[LAYER-1][CUP-1]);  
    //for(i=1; i<LAYER; i++){for(j=2; j<CUP; j++){printf("%d\t", route[i][j]);} printf("\n");}  
    return 0;  
}  

输出结果为：MIN STEP IS 14。也就是，有一种方法，最多需要试摔14次。同时route数组打印出了方法。
比如route数组的结果：

因此，route[100][2]=14，第一次试摔是在14层，如果碎了，那么从第一层开始往14层试摔，如果没碎，第二次试摔是在route[100-14][2]=route[86][2]=13，也就是在14+13=27层进行第二次试摔，如果这次碎了，那么从第14+1=15层开始向上试摔，如果这次没碎，第三次试摔是在route[86-13][2]=route[73][2]=12，也就是在27+12=39层开始试摔，依次类推。