Cost of guessing Number Higher or Lower

Problem: We are playing the Guessing Game. The game will work as follows:

• I pick a number between 1 and n.
• You guess a number.
• If you guess the right number, you win the game.
• If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
• Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

Example:

Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is 0. Otherwise, you pay 1.
    - If my number is higher, it must be 2. Guess 2. Your total is 1.
The worst case is that you pay 1.

Approach: Let's take an example say n = 10. Say I guess is 7, Now what will happen if this is a wrong guess. I have to pay Rs. 7, Now depends on whether the picked number was less than or more than 7, My next guess will be either one of 1...6 or one of 8...10 so I can say that I need minimum 7 + Maximum of money required for 1...6 and money required for 8...10. That means we can say that for any k, money required is:

k + Max(MoneyRequired(1...k-1), MoneyRequired(k+1...n))

Right! That means if we do it for every k = 1 to n, and take the maximum of it. It will our answer. You can see this actually leads to recursive approach and it can easily be solved using recursion but it will take a lot of time. 

If you look at the recursion closely, you can see we are solving the same sub problems many times. This tells us that we can use DP here. Basically we can have 2D Table where Table[i][j] will tell the maximum money required for range [i...j]. Once we solved this problem using recursion for a range [i...j], we can store it in the Table and next time whenever we need to solve this problem again for [i...j], we can simply return it from the Table.

That's it!

Implementation in C#:

        public static int GetMoneyAmount(int n)

        {

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

            for (int i = 0; i <= n; ++i)

            {

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

                {

                    table[i, j] = int.MaxValue;

                }

            }

            return GetMoneyAmount(1, n, table);

        }

        private static int GetMoneyAmount(int start, int end, int[,] table)

        {

            if (start >= end)

            {

                return 0;

            }

            if (table[start, end] != int.MaxValue)

            {

                return table[start, end];

            }

            for (int i = start; i <= end; ++i)

            {

                table[start, end] = Math.Min(table[start, end], i + Math.Max(GetMoneyAmount(start, i - 1, table), GetMoneyAmount(i + 1, end, table)));

            }

            return table[start, end];

        }

Complexity: O(n^2)