丢棋子问题

# -*- coding: utf-8 -*-

import math


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回最差情况下扔棋子的最小次数
# @param n int整型 楼层数
# @param k int整型 棋子数
# @return int整型
#
class Solution1:
    """
    题目：
        https://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266?tpId=196&tqId=37178&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=2&tags=&title=
    算法1：
         # 超时 ！！！！！

        设dp[i][j]表示i层楼，j个棋子，在最差情况下的最少试验次数
        初始化：
            dp[0][0] = 0
        状态转移方程：
            dp[i][0] = 0 # i层楼，0个棋子，无须试验
            dp[i][1] = i # i层楼，1个棋子，试验 i 次
            dp[0][j] = 0 # 0层楼，j个棋子，无须试验
            dp[1][j] = 1 # 1层楼，j个棋子，试验 1 次
            dp[i][j] = min(1 + max(dp[k - 1][j - 1], dp[i - k][j])), 1 <= k <= i，这里选取从第k层扔下一个棋子，如果碎了，那么大于k的楼层必然会碎，问题变为 k - 1 层楼，j - 1个棋子进行试验；如果没碎，那么小于k的楼层必然不碎，问题转变为i - k层楼，j个棋子进行试验。另外需要注意的是，没经过一次试验，次数+1。同时我们取得是最少试验次数。
        返回值：
            dp[n][k]
    复杂度：
        时间复杂度：O(n^2 * k)
        空间复杂度：O(n * k)
    """

    def solve(self, n, k):
        # write code here
        dp = [[10 ** 6] * (k + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            dp[i][1] = i
        for j in range(1, k + 1):
            dp[1][j] = 1

        for i in range(2, n + 1):
            for j in range(2, k + 1):
                for l in range(1, i + 1):
                    dp[i][j] = min(dp[i][j], 1 + max(dp[l - 1][j - 1], dp[i - l][j]))

        return dp[n][k]


class Solution:
    """
    参考：
        大神：棒棒糖🍭201906101800876
    算法：
        设dp[i][j]表示i个棋子扔j次, 最多能测多少层。考虑第i个棋子在最优的楼层扔下去, 有两种情况:
            a. 碎了, 那么上面就不用测了, 下面能测的是dp[i-1][j-1]层
            b. 没碎, 那么下面就不用测了, 上面能测dp[i][j-1]层
            c. 第i个棋子扔掉的那一层也能测.
        综上，状态转移方程：
            dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
        显然dp[i][j]是单调递增的, 那么我们要求的答案就是在i不超过k的情况下, 使得dp[i][j] >= n的最小的j。
        不难发现，dp[i][j]只和上面元素和左上面元素有关系， 故可以压缩一维，并且需要逆向计算。在计算dp[i][j]的时候，先从右侧开始计算，算到i的时候，一开始dp[i]处为黄色，存储的是上一次迭代的结果dp[i][j-1], i-1处也为黄色，因此dp[i] = dp[i] + dp[i-1] + 1就等价于dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1。如果反了，那么算到i的时候， i-1处就变成了粉色，转移方程就相当于dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1, 导致wa
    复杂度：
        时间复杂度：O(klogn)
        空间复杂度：O(k)
    """

    def solve(self, n, k):
        # write code here
        if n == 0:
            return 0
        if k == 1:
            return n

        b = int(math.log10(n) / math.log10(2)) + 1  # 优化性质, 如果k充分大, 二分的扔即可，python27没有math.log2(x), 数学替代：log2(n) = log10(n)/log10(2)
        if k >= b:
            return b

        dp = [1] * (k + 1)  # 初始值, 不管有几个棋子, 扔1次只能测1层
        res = 1  # 最少扔1次

        while True:
            res += 1  # 每一轮迭代, j增加1次
            for i in range(k, 1, -1):
                dp[i] = dp[i] + dp[i - 1] + 1
                if dp[i] >= n:  # 当前尝试的楼层到达n，找到解
                    return res
            dp[1] = res  # dp[1][j] = j，1个棋子扔j次，测得楼层为j


if __name__ == '__main__':
    s = Solution()

    # n, k = 10, 1

    # n, k = 3, 2

    # n, k = 105, 2

    # n, k = 874520, 7

    n, k = 1, 1000000

    res = s.solve(n, k)

    print res