# README

375. Guess Number Higher or Lower II

Solution idea

Also known as Min-max problem; interval DP problem.

Define DP[i][j] as the min cost to guess for an interval [i...j].

Top-down: Recursion + DP Memoization (easy to understand)

Key 1: Take mx of left-half subarray and right-half subarry. This is because we need a cost that can cover both halves
Key 2: Out of all split points, choose the one that gives the min cost.

Time complexity = $O(n^2*n) = O(n^3)$

Space complexity = $O(n^2)$

Time complexity Explanation:

With memoization, the algorithm has no repeated recursion, meaning that we split into and traverse each continuous subarray only once. For an array of lenth $n$, the total number of continuous subarray is $O(1+2+3+\cdots+n) = O(\frac{n(n+1)}{2}) = O(n^2)$. For each subarray, we traverse each element fo find the best splitting point, which is $O(n)$. Therefore, in total, the time complexity = $O(n^3)$.

Bottom-up: DP

如果解题角度是，从小区间开始先算再往大区间算，则 DP 的两层for-loop 为:

外层loop是循环 length：从最小的length的区间开始，逐步增长
内层loop是循环 start position: 这里要注意，最大的start position 加上length后不能越界, 终止条件要注意用 j-i+1=len => j=i+len-1 => i <= i+len-1

DP 的loop 搭建好了以后，要考虑边界条件：

考虑循环的边界取值带入 update DP 的步骤时，会不会发生越界。要把越界的值提前算好 (默认值设成0？还是无限大/小？此题设成0)。

Time complexity = $O(n^2*n) = O(n^3)$

Space complexity = $O(n^2)$

Resource

Top-down: 【递归 + 动态规划】leecode 375 Guess Number Higher or Lower II

Bottom-up: 【每日一题】375. Guess Number Higher or Lower II, 04/27/2019; wisdompeak/LeetCode

Time complexity analysis: DP and memo solution explanation

Total number of continuous subarrays: The total number of subarrays