第375题---Guess Number Higher or Lower II

• 题意描述：
  • 给定一个数字n,进行猜数游戏，判断高低。求完成猜数的至少的花费

• 思路：动态规划(完全不懂)

  • vector> 存放的是从i到j的最小花费，对于数x，则完成的max的dp(vecs, i, x-1)和dp(vecs, x+1, j)的最大值+x；则最小花费为min(res, 上面的值)，然后把对应的vec[i][j]赋值

• 代码

  class Solution {
  public:
      int getMoneyAmount(int n) {
          vector<int> vec(n+1, 0);
          vector<vector <int>> vecs(n+1, vec);
          return DP(vecs, 1, n);
      }
      
      int DP(vector<vector <int>>& t, int s, int e) {
          if(s >= e)
              return 0;
          if(t[s][e] != 0)
              return t[s][e];
          int res = INT_MAX;
          for(int i = s; i <= e; ++ i) {
              int temp = i + max(DP(t, s, i-1), DP(t, i+1, e));
              res = min(res, temp);
          }
          t[s][e] = res;
          return res;
      }
  };