375猜数字大小II

题目：我们正在玩一个猜数游戏，游戏规则如下：我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

来源：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/

法一：参考别人后自己的代码

思路：动态规划这个题不是简单的二分法，而是先取一个数分割后，取左右两边的最大值，最后再取最小值，注意动态规划问题一定要先定义dp数组，再列几个简单情况的表，切忌不动手空想。这个题里处理边界条件方法是：不处理长度为1和2的数组，至少从3开始处理。

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * n for i in range(n)]
        for i in range(n-1):
            dp[i][i+1] = i+1
        for start_col in range(2,n):
            row = 0
            for col in range(start_col, n):
                # 这里是关键，先取最大值，后取最小值
                dp[row][col] = min( max(dp[row][i-1], dp[i+1][col]) + (i+1) for i in range(row+1, col))
                row += 1
        return dp[0][-1]
if __name__ == '__main__':
    duixiang = Solution()
    # a = duixiang.getMoneyAmount(n=20)
    # a = duixiang.getMoneyAmount(n=10)
    # a = duixiang.getMoneyAmount(n=5)
    a = duixiang.getMoneyAmount(n=1)
    print(a)

View Code

法二：最开始的方法

思路：利用递归，每次拆分后取左右两边中的最大值，再取不同拆分方法中的最小值，