public class Solution {

    public int GetMoneyAmount(int n)

        {

            int[,] table = new int[n + , n + ];

            return DP(table, , n);

        }

        int DP(int[,] t, int s, int e)

        {

            if (s >= e) return ;

            if (t[s, e] != ) return t[s, e];

            int res = int.MaxValue;

            for (int x = s; x <= e; x++)

            {

                int tmp = x + Math.Max(DP(t, s, x - ), DP(t, x + , e));

                res = Math.Min(res, tmp);

            }

            t[s, e] = res;

            return res;

        }

}

public class Solution {

    public int GetMoneyAmount(int n)

        {

            int[,] table = new int[n + , n + ];

            for (int j = ; j <= n; j++)

            {

                for (int i = j - ; i > ; i--)

                {

                    int globalMin = int.MaxValue;

                    for (int k = i + ; k < j; k++)

                    {

                        int localMax = k + Math.Max(table[i, k - ], table[k + , j]);

                        globalMin = Math.Min(globalMin, localMax);

                    }

                    table[i, j] = i +  == j ? i : globalMin;

                }

            }

            return table[, n];

        }

}