# 0375. Guess Number Higher or Lower II
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/guess-number-higher-or-lower-ii/
## 思路
边界条件:
如果i==j dp[i][j]=0 猜都不用猜
如果i>j 需要让dp[i][j]不影响结果 所以直接等于0即可
因为过程中可能遇到k-1和k+1 为了让它合法(因为k可能等于0和n)
扩大了dp的size从```n*n```变成```(n+2)*(n+2)```
## Code

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