I use divide and conquer. Basically, loop through 1 to 18 and use each as the divider. Then the left and right part become subproblems. The outer loop computes and stores the optimal cost and #oflookup for values smaller than 18.

For example, my code use the bold italic as seperator:

1,2,3,4,5,6,** 7**,8,9,10,11,12,13,14,15,16,17,18

The code computes

left = getMoneyAmount(6)

right = getMoneyAmount(11) + #oflookup(11) * 7 (seperator value)

Since right > left, and right < all other possible solution, 7 is taken as the seperator.

Then 15 and 17 are taken as the seperator.

8,9,10,11,12,13,14,** 15**,16,17,18

16,

**,18**

*17*So 7 + 15 + 17 = 39.

Here's the code:

```
class Solution {
public:
unordered_map<int,pair<int,int>> dp; //cost, #oflookup
int getMoneyAmount(int n) {
dp[1] = make_pair(0,0);
dp[2] = make_pair(1,1);
dp[3] = make_pair(2,1);
dp[4] = make_pair(4,2);
if(n < 4) return dp[n].first;
int mid = 3;
for(int r = 5; r <= n; r++){
dp[r] = make_pair(INT_MAX,INT_MAX);
for(int mid = 1; mid <= r; mid++){
int left = mid + dp[mid - 1].first;
int right = mid + dp[r - mid].first + dp[r - mid].second * mid;
int leftcount = 1 + dp[mid - 1].second;
int rightcount = 1 + dp[r - mid].second;
if(left > right && dp[r].first > left){
dp[r] = make_pair(left,leftcount);
cout << r << " left: " << left << " " << leftcount << " " << mid << endl;
} else if(left <= right && dp[r].first > right) {
dp[r] = make_pair(right,rightcount);
cout << r << " right: " << right << " " << rightcount << " " << mid << endl;
}
}
}
return dp[n].first;
}
};
```