/*
* 算法思想：
* 维护一个二维数组arr[n+1][n+1]，其中arr[i][j]表示从i开始到j，猜正确所需要的最少钱
*
* 详见参考：http://www.cnblogs.com/fayin/p/10407176.html
*/
inline int min(int a, int b){
return a<b ? a:b;
}
inline int max(int a, int b){
return a>b ? a:b;
}
int get(int start, int end, int n, int arr[n+1][n+1]){
int i;
if(end-start <= 0){
if(end==start) arr[start][end] = 0;
return 0;
}
if(end-start == 1) {
arr[start][end] = start;
return start;
}
if(arr[start][end] != INT_MAX) return arr[start][end];
for(i=start; i<=end; i++){
/* 对每个位置i进行访问，表示选取当前i位置猜后，可以猜得对；
* 每个位置所需钱为max(i+get(start, i-1, n, arr), i+get(i+1, end, n, arr)
* 因为有可能落在两侧，所以取max；
* 每个i位置都能才对，因此选取最小的一个作为最后所需要的钱。
*/
arr[start][end] = min(arr[start][end], max(i+get(start, i-1, n, arr), i+get(i+1, end, n, arr)));
}
return arr[start][end];
}
int getMoneyAmount(int n){
int i=1, j;
int arr[n+1][n+1];
for(i=0; i<n+1; i++){
for(j=0; j<n+1; j++){
arr[i][j] = INT_MAX;
}
}
return get(1, n, n, arr);
}
