Intuitively, to minimize cost, you should always first choose a number in larger half range, i.e. find the `weighted balance point`

```
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> cache(n+1, vector<int>(n+1, 0));
return cost(cache, 1, n);
}
int cost(vector<vector<int>>& v, int l, int r) {
if (l >= r) return 0;
if (v[l][r] != 0) return v[l][r];
int res = INT_MAX;
int start = l + (r - l) / 2;
for (int i = start; i <= r; ++i) {
int lc = cost(v, l, i-1);
int rc = cost(v, i+1, r);
int tmp = i + std::max(lc, rc);
res = std::min(res, tmp);
if (lc >= rc) break;
}
v[l][r] = res;
return res;
}
};
```