func getMoneyAmount(n int) int {
	dp := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	return search(dp, 1, n)
}

func search(dp [][]int, beg, end int) int {
	if end <= beg {
		return 0
	}
	if dp[beg][end] != 0 {
		return dp[beg][end]
	}
	dp[beg][end] = 1<<32 - 1
	for i := beg; i <= end; i++ {
		left := search(dp, beg, i-1)
		right := search(dp, i+1, end)
		min := i + maxInt(left, right) // Prepare for the worst, but do your best
		if min < dp[beg][end] {
			dp[beg][end] = min
		}
	}
	return dp[beg][end]
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}