Участник:Михеева Анастасия Максимовна/Guess Number Higher or Lower II

Ссылки сюда (1) →

class Solution {
public:
   int cost(int low, int high, vector < vector <int> >& dp){
      if(low >= high)return 0;
      if(dp[low][high] != -1)return dp[low][high];
      int ans = INT_MAX;
      for(int i = low; i <= high; i++){
         ans = min(ans, i + max(cost(low, i - 1, dp), cost(i + 1, high, dp)));
      }
      return dp[low][high] = ans;
   }
   int getMoneyAmount(int n) {
      vector < vector <int> > dp(n + 1, vector <int> (n + 1, -1));
      return cost(1, n, dp);
   }
};