LC Trick to Prevent TLE: Static Variables

The solution to the problem below without the static "memo" (inspired by DP memoization) leads to TLE. Since the solution for test case N can be leveraged by test cases M (where M>N), you can use a static variable to cache some of the previously seen results. This is perfectly legal in LC land. Code is down below, cheers, ACC.

Minimum Cost to Split into Ones II - LeetCode

You are given an integer n.

In one operation, you may split an integer x into two positive integers a and b such that a + b = x.

The cost of this operation is a * b.

Return the minimum total cost required to split the integer n into n ones.

 

Example 1:

Input: n = 3

Output: 3

Explanation:

One optimal set of operations is:

x	a	b	a + b	a * b	Cost
3	1	2	3	2	2
2	1	1	2	1	1

Thus, the minimum total cost is 2 + 1 = 3.

Example 2:

Input: n = 4

Output: 6

Explanation:​​​​​​​

One optimal set of operations is:

x	a	b	a + b	a * b	Cost
4	2	2	4	4	4
2	1	1	2	1	1

Thus, the minimum total cost is 4 + 1 + 1 = 6.

 

Constraints:

• 1 <= n <= 5 * 107

public class Solution {
        static Hashtable memo = new Hashtable();
        
        public long MinCost(int n)
        {
            return MinCostMemoization(n);
        }

        private long MinCostMemoization(int n)
        {
            if (n == 1) return 0L;

            if (memo.ContainsKey(n))
                return (long)memo[n];

            int a = n / 2;
            int b = n - a;

            long retVal = (1L * a * b) + MinCostMemoization(a) + MinCostMemoization(b);

            if (!memo.ContainsKey(n))
                memo.Add(n, retVal);

            return retVal;
        }
}