vivek_ragi

GUESS_NUMBER_HIGHER_OR_LOWER_2

Jun 17th, 2021
698
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int getMoneyAmount(int n) {
  4.         vector<int> arr(n);
  5.         int dp[n + 3][n + 1];
  6.         memset(dp,0,sizeof(dp));
  7.        
  8.         //O(n^2 * n) = O(n^3)
  9.         for(int len = 2; len <=n; ++len) {
  10.             for(int start = 1; start + len <= n + 1; ++start) {
  11.                 int end = start + len - 1;
  12.                 int mn = INT_MAX;
  13.                
  14.                 for(int element = start; element <= end; ++element) {
  15.                     mn = min(mn, element + max(dp[start][element - 1], dp[element + 1][end]));
  16.                 }
  17.                  dp[start][end] = mn;
  18.             }
  19.            
  20.         }
  21.        
  22.         return dp[1][n];
  23.     }
  24. };
RAW Paste Data