leetcode 374

图片.png

这道题很简单，但我在写的时候还是二分法出错：

• 注意
  为了防止死循环+溢出，我们选用int mid=left + (right - left) / 2;
  最后返回左或者右都可以：

int guessNumber(int n) {
        if(guess(n)==0)
            return n;
        int left=1,right=n;
        while(left<right){
            int mid=left + (right - left) / 2;
            int ans=guess(mid);
            if(ans==0)
                return mid;
            if(ans==1)
                left=mid;
            else
                right=mid;
        }
        return left;
    }

---

leetcode 375

图片.png

• 例子：
  n=1: 最小只能是1
  n=2:最小只能是1
  n=3:有1 2 3 ：如果猜1，错误的情况 最小是1+2；所以最小只能是2
  n=4:有1 2 3 4：分情况讨论：

当k为1时，左区间为空，所以cost为0，而右区间2，3，4，根据之前的分析应该取3，所以整个cost就是1+3=4。

当k为2时，左区间为1，cost为0，右区间为3，4，cost为3，整个cost就是2+3=5。

当k为3时，左区间为1，2，cost为1，右区间为4，cost为0，整个cost就是3+1=4。

当k为4时，左区间1，2，3，cost为2，右区间为空，cost为0，整个cost就是4+2=6。

综上k的所有情况，此时我们应该取整体cost最小的，即4，为最后的答案

int helper(int start,int end,vector<vector<int>>& dp){
        if (start >= end) 
            return 0;
        int ans=INT_MAX;
        if(dp[start][end]>0)
            return dp[start][end];
            
        for(int i=start;i <=end;i++){
            int money=i+max(helper(start,i-1,dp),helper((i+1),end,dp));
            ans=min(ans,money);
        }
        dp[start][end]=ans;
        return dp[start][end];
    }
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        return helper(1,n,dp);
    }