dp(1,2) =
Min(Max(0, 2) , max(1, 0))
答案是a
选中第k个值时
dp(i, j) = dp(i, k-1) + dp(k+1, j)
答案是左侧：
max(0, k + dp(i，k-1), dp(k + 1, j) + )
第一次猜测 x：
dp(i, j) = max(0, dp(i, x - 1) + x, dp(x + 1, j) + x) = max(dp(i, x - 1), dp(x + 1, j)) + x
x = i时：
dp(i，j) = max(0, dp(x + 1, j) + x) = max(0, dp(x + 1, j)) + x
#define N 250
int g_Data[N][N] = {0};
int max(int x, int y)
{
if (x > y) {
return x;
} else {
return y;
}
}
int min(int x, int y)
{
if (x < y) {
return x;
} else {
return y;
}
}
int dp(int x, int y)
{
if (x > y) {
return 0;
}
if (x == y) {
return 0;
}
if (g_Data[x][y] > 0) {
return g_Data[x][y];
}
int res = 0xFFFFFF;
for (int i = x; i <= y; i++) {
int tmp = max(dp(x, i - 1), dp(i + 1, y)) + i;
res = min(res, tmp);
}
g_Data[x][y] = res;
return res;
}
int getMoneyAmount(int n)
{
return dp(1, n);
}