丢棋子问题

python解法
思想：dp[i][j]=dp[i][j-1]+ dp[i-1][j-1]+1
dp[i][j-1]：当前棋子没有碎
dp[i-1][j-1]：当前棋子碎了
1：当前棋子占用1次

from functools import lru_cache
class Solution:
    def solve(self , n , k ):
        # write code here
        @lru_cache()
        def fun(qi, n):
            if qi == 1: return n
            if n == 1: return 1
            return fun(qi,n-1) + fun(qi-1,n-1) + 1
        res = 1
        while fun(k, res) < n:
            res += 1
        return res

import java.util.*;


public class Solution {
    public int solve (int n, int k) {
        int[] dp = new int[k + 1];
        int m = 0;

        while (dp[k] < n) {
            m++;
            for (int j = k; j > 0; j--) {
                dp[j] = dp[j] + dp[j - 1] + 1;
            }
        }

        return m;
    }
}

这是根据各位大神的解法，拼凑出来的一种我可以看懂，而且可以通过的解法（动态规划+二分优化+空间优化）

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        int[] pre = new int[n + 1];
        int[] dp = new int[n + 1];
        int res = (int) (Math.log(n) / Math.log(2)) + 1;
        if (res <= k) return res;
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }
        for (int i = 2; i <= k; i++) {
            pre = dp;
            dp = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                int l = 0;
                int r = j;
                while (l < r) {
                    int mid = (l + r) / 2;
                    int idx = j - 1 - mid;
                    if (r - l <= 1) {
                        dp[j] = 1 + Math.max(dp[l], pre[r]);
                        break;
                    }
                    if (pre[mid] == dp[idx]) {
                        dp[j] = dp[idx] + 1;
                        break;
                    }
                    if (pre[mid] > dp[idx]) {
                        r = mid;
                    } else {
                        l = mid;
                    }
                }
            }
        }
        return dp[n];
    }
}

# -*- 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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        // write code here
        /******************************************************************************************************/
        // 最原始的方法(最好理解)
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                for (int x = 1; x <= j; x++) {
                    dp[i][j] = Math.min(Math.max(dp[i - 1][x - 1], dp[i][j - x]) + 1, dp[i][j]);
                }
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 使用二分查找
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                int l = 1;
                int r = j;
                int mid;
                while (l < r) {
                    mid = l + ((r - l) >> 1);
                    if (dp[i - 1][mid - 1] < dp[i][j - mid]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                dp[i][j] = Math.min(Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1, dp[i][j]);
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 楼层高肯定比楼层低所需要的查找次数要多
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            int x = 1;
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                while (dp[i - 1][x - 1] < dp[i][j - x]) {
                    x++;
                }
                dp[i][j] = Math.min(Math.max(dp[i - 1][x - 1], dp[i][j - x]) + 1, dp[i][j]);
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 使用滚动数组的方式，优化存储空间
        int[][] dp = new int[2][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        int cur;
        int pre;
        for (int i = 2; i <= k; i++) {
            int x = 1;
            cur = i % 2;
            pre = i % 2 == 0 ? 1 : 0;
            for (int j = 1; j <= n; j++) {
                dp[cur][j] = j;
                while (dp[pre][x - 1] < dp[cur][j - x]) {
                    x++;
                }
                dp[cur][j] = Math.min(Math.max(dp[pre][x - 1], dp[cur][j - x]) + 1, dp[cur][j]);
            }
        }
        return dp[k % 2][n];
    }
}

class Solution:
    def solve(self , n: int, k: int) -> int:
        # write code here
        memo={}
        def dp(n,k):
            if k==1:return n
            if n==0:return 0
            if (n,k) in memo.keys():
                return memo[(n,k)]
            res=float('Inf')
            left=1
            right=n
            while left<=right:
                mid=(left+right)//2
                broken=dp(mid-1,k-1)
                no_broken=dp(n-mid,k)
                if broken>no_broken:
                    res=min(res,broken+1)
                    right=mid-1
                else:
                    res=min(res,no_broken+1)
                    left=mid+1
            memo[(n,k)]=res
            return res
        return dp(n,k)