LeetCode刷题实战375：猜数字大小 II-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 猜数字大小 II，我们先来看题面：

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

We are playing the Guessing Game. The game will work as follows:

I pick a number between 1 and n.

You guess a number.

If you guess the right number, you win the game.

If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.

Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

示例

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

解题

https://blog.csdn.net/abc15766228491/article/details/82931660

具体思路，经典的动态规划问题:

1、设置dp[len][i] 表示的意思是，长度是len的数字段，以下标为i开头的最佳解（最小花费值）。首先初始化前两行dp[0][i]和dp[1][0]为0，意思为，长度为0和1的数字段的花费都为0，初始化dp[2][i]为dp[2][i]=a[i]表示，以下标i开头，长度为2的段，最佳解为a[i]（比如，（2，3）这个段的最佳值为2）。

2、设置dp[len][i]：遍历以i开头，长度为len的所有数字，以每一个数字的位置作为切分点，切分这个段为左右两个部分，比较左右两个部分的值，取最大值保存，遍历所有数字，得到所有的切分点下的最大值，取最小值，这个值就是dp[len][i]的值，即：部分取最大，全局取最小。动态归化方程：

dp[len][i] = min( splitResult(j) ) (0<=j<=len)；splitResult(j) = max(dp[t][i], dp[len-t-1][j+i+1])+a[j+i] (0<=t<len)；

这里j+i是遍历小数字段时候的切分点

因此，用三重循环就可以了,最后一行dp[n]只有一个值，就是从dp[n][0]，意思就是说从0开始长度为n的数据段的最优解，返回就行。

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int> >dp(n+1, vector<int>(n+1, 0));
        vector<int> a;
        for (int i = 0; i < n; ++i) {
            a.push_back(i+1);
        }
        for (int i = 0; i < n-1; ++i) {
           dp[2][i]=a[i];
        }
        for (int len = 3; len <= n; ++len) {
            //开始求dp[3][i]
            for (int i = 0; i <= n-len; ++i) {
                //对于每个dp[3][i]都要遍历每个值，进行且分，找到且分点的cost最小的值为dp[3][i]的值
                int global=0;
                for (int j = 0; j < len; ++j) {
                    //对于每次切分之后的两个部分，取最大值,j是长度，从下标偏移位置为j的地方切分，左边长度为j，右边长度为len-j-1
                    //左边开始的值为i,右边开始的值为j+i+1,切分点为j+i
                    int tmp = max(dp[j][i], dp[len-j-1][j+i+1])+a[j+i];
                    //部分最大，整体最小
                    if(j==0) global = tmp;
                    else global = min(global, tmp);
                }
                dp[len][i] = global;
            }
        }
    
        return dp[n][0];
    }
};