腾讯大厦有39层，你手里有两颗一抹一眼的玻璃珠。当你拿着玻璃

用户随机选一层i，扔下去，有两个结果：

碎掉，或者没有碎掉。

1.如果碎掉，去试验前i-1层，那么最多需要i-1次再加上碎掉的那一次，最多就是i次。

2.如果没有碎掉，等于说从第i+1层往后，也还是有两个弹珠，这就回到了递归的思路上了。
在这种没有碎掉的情况下，假如总共有N层，那么N层的最多次数等于N-i层的最多次数。所以

针对用户随机选择的这一层i， 以上1和2两种情况， 求其最大值就是最差情况下的次数。

用户随机选择的这个i，也可以变化的，取值 1,2,3...N. 那么我们就会得到不同的值。
针对1,2,3...N. 会有N个，所有这些值中取最小，就是最优解。  用F（N）表示这个最优解，那么F（0）由于没有楼层，所以一定等于0，也就是说不需要实验。
F（0） = 0;
F（N）= min（max（1, F(N-1) + 1)， max（2， F（N-2）+ 1)... max(N, F（0）+ 1））

F（0） = 0;
F（1） = 1;
F (2) = min(max(1, F(1）+ 1）， max（2， F（0） + 1）） = 2；

可以使用递归算法求得其值，最终的结果是9次。

package interview;

import java.util.ArrayList;

public class ThrowPinballFrom30Layer {
	/**
	 * 腾讯大厦有39层，你手里有两颗一抹一眼的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。大厦有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，
	 * 等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式来确定临界楼层
	 * 
	 * @param 39
	 *            layer
	 * @return the optimal step for the first ball.
	 */
	public static int getOptimalStep(int N, int[] results, int[] selection) {

		if (N == 0) {
			results[N] = 0;
			return 0;
		}
		if (results[N - 1] >= 0) {
			return results[N - 1];
		}

		int selectedIndex = 0;
		int min = -1;
		for (int i = 0; i < N; i++) {
			int max = Math.max(i + 1, getOptimalStep(N - i - 1, results, selection) + 1);
			if (min < 0) {
				min = max;
				selectedIndex = i;
			} else {
				if (min > max) {
					selectedIndex = i;
					min = max;
				}
			}
		}
		selection[N - 1] = selectedIndex;
		results[N - 1] = min;
		return min;
	}

	public static void main(String[] args) {

		int N = 39;
		int[] results = new int[N];
		for (int i = 0; i < results.length; ++i) {
			results[i] = -1;
		}
		int[] selection = new int[N];

		System.out.println("optimal steps:" + getOptimalStep(N, results, selection));

		ArrayList<Integer> steps = new ArrayList<>();
		int current = N - 1;
		int selectPosition = 0;
		while (true) {
			if (current < 0) {
				break;
			}
			selectPosition = selectPosition + selection[current];
			steps.add(selectPosition);

			selectPosition = selectPosition + 1;

			current = N - 1 - selectPosition;
		}

		StringBuilder sb = new StringBuilder();
		
		sb.append("selections:");
		sb.append("[");
		for (int i = 0; i < steps.size(); ++i) {
			if (i != 0) {
				sb.append(",");
			}
			sb.append(steps.get(i) + 1);
		}
		sb.append("]");

		System.out.println(sb.toString());
	}
}

这是道动态规划
设函数F(x)为X层大厦时,最坏情况的最小值
比39层大厦,假设我再5楼仍两种结果
1.碎了,那么临界楼就在5楼内,接下来从1楼一层层往上试验。
2.没碎,此时问题相当于在34层大厦中找临界楼即F(34),最后再+1(这是dp的特征:最优子结构)
从5楼仍珠子的最坏情况:max(5,F(34)+1)
那么问题是怎么找最优,其实5楼是我自己随便挑的,我可以把每一楼都试过去
max(1,F(38)+1),max(2,F(37)+1)...max(39,F(0)+1)
恩,我列出了所有方案的最坏情况,接着从他们中找到"最坏的情况扔的次数比其他任何方式最坏的次数都少"
min(max(1,F(38)+1),max(2,F(37)+1)...max(39,F(0)+1))
整理公式(状态转移方程)
F（N）=Min（Max（1，1+F（N-1）），Max（2，1+F（N-2）），……，Max（N-1，1+F（1）））

	1



	2     10



	3     11       18



	4     12       19     25



	5     13       20     26     31



	6     14       21     27     32       36



	7     15       22     28     33       37



	8     16       23    29      34       38



	9     17       24     30      35       39



	



	先从最后一行开始测试，当碎了时，再从该列最上方测试，所以最多需要9次；

第一个球测试楼层顺序 8-15-21-26-30-33-35-37-39，碎后第二个球自上一个测试层上一层依次测试

由于是球的损坏性，切考虑的性能为“最坏的情况扔的次数”，所以需要尽可能分成每段最差情况需要测试次数相同，如上分段后，最差情况,33，34，36，37，38，39层，需要测试9次，其余每段的的最差情况为8次。

class Solution{

    static int solution(int num){
        int[]dp=new int[num+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=num;i++){
            for(int j=1;j<=i;j++){
                dp[i]=Math.min(Math.max(j,dp[i-j]+1),dp[i]);
            }
        }
        return dp[num];
    }
    public static void main(String[]args){
        System.out.print(solution(39));
    }
}

以后路过腾讯大厦前要注意防护

#include <iostream>
using namespace std;

inline int max(int a, int b) { return a > b ? a : b; }

int miniFloorR(int maxFloor)
{
	if (maxFloor == 0) return 0;
	if (maxFloor == 1) return 1;

	int ret = maxFloor;
	for (int i = 0; i < maxFloor; i++)
	{
		int tmp = max(i + 1, miniFloorR(maxFloor - i - 1) + 1);
		if (ret > tmp) ret = tmp;
	}

	return ret;
}

int miniFloorI(int maxFloor)
{
	int *arra = new int[maxFloor + 1];

	for (int i = 0; i <= maxFloor; i++)
	{
		arra[i] = i;
		for (int j = 1; j <= i; j++)
		{
			int tmp = max(j, arra[i - j] + 1);
			if (tmp < arra[i])
				arra[i] = tmp;
		}
	}
	
	int ret = arra[maxFloor];

	delete arra;

	return ret;
}

int main()
{
	cout << "Result: " << miniFloorI(39) << endl;

	return 0;
}

package prac_tencent;

public class dp_boli {

    static int[][] dp;

    static int INF = 0x3f3f3f;

    public static void main(String[] args) {

        int N = 39;

        int M = 2;

        dp = new int[N + 1][M + 1];

        for (int i = 0; i <= N; i++) {

            for (int j = 0; j <= M; j++) {

                dp[i][j] = INF;

            }

        }

        int dfs = dfs(N, M);

        System.out.println(dfs);

    }

    public static int dfs(int n, int m) {

        if (dp[n][m] != INF) {

            return dp[n][m];

        }

        if (n == 0) {

            return dp[n][m] = 0;

        }

        if (m == 1) {

            return dp[n][m] = n;

        }

        for (int i = 1; i <= n; i++) {

            dp[n][m] = Math.min(dp[n][m], 1 + Math.max(dfs(i-1, m-1), dfs(n-i, m)));

        }

        return dp[n][m];

    }

}