2021-11-12 375猜数字大小

动态规划的思路，注意此题似乎没法用二分直接做，相反似乎是先猜比选择的数字大的，然后再向下寻找，最终找到选择的数字i,接着构造动态规划方程，dp[i][j]=k+Math.max(dp[i][k-1]，dp[k+1][j]);
最终找出k从i到j内所有可能情况的最小值。
java版本

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp=new int[n+1][n+1];
        for(int i=n-1;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                int minCost=Integer.MAX_VALUE;
            for(int k=i;k<j;k++){
               int   cost=k+Math.max(dp[i][k-1],dp[k+1][j]);
               minCost=Math.min(minCost,cost);
            
            }
           dp[i][j]=minCost;
            }
            
         }
           return dp[1][n];
 
        }

    }

Go版本

import ( "math"
"fmt")
func getMoneyAmount(n int) int {


   dp:=make([][]int,n+1)

   for i:=range dp{
       dp[i]=make([]int,n+1)
   }

    // i表示提供的数字
    // j表示每次初始猜测的数字
    // k表示猜测数字与实际数字相差的后续猜测数
//    INT_MAX:= int(^uint(0) >> 1)
   minCost:=0;


   for i:=n-1;i>=1;i--{
    for j:=i+1;j<=n;j++{
        minCost=math.MaxInt32;
        for k:=i;k<j;k++{
            cost:=k+max(dp[i][k-1],dp[k+1][j])
            minCost=min(cost,minCost);

        }
        dp[i][j]=minCost;
    }
   }
//    fmt.Println(dp)

    return dp[1][n];
}

func  min(num1 int,num2 int)int{
if num1>num2{
    return num2;
}
return num1;
}
func  max(num1 int,num2 int)int{
if num1>num2{
    return num1;
}
return num2;
}