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

Материал из DISCOPAL
< Участник:Михеева Анастасия Максимовна
Версия от 20:48, 23 мая 2020; Михеева Анастасия Максимовна (обсуждение | вклад) (Новая страница: «<code-cpp> class Solution { public: int cost(int low, int high, vector < vector <int> >& dp){ if(low >= high)return 0; if(dp[low][high] != -1)retur…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
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);
   }
};