LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax

https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/

	class Solution {
	/**
	* @param n
	* @return
	*/
	public int getMoneyAmount(int n) {
	if (n < 2) {
	return 0;
	}
	// core logic
	table = new int[n + 1][n + 1];
	return dp(1, n);
	}
	private int[][] table;
	private int dp(int start, int end) {
	if (start >= end) {
	return 0;
	}
	if (table[start][end] != 0) {
	return table[start][end];
	}
	int min = Integer.MAX_VALUE;
	for (int i = start; i <= end; i++) {
	int res = i + Math.max(dp(start, i - 1), dp(i + 1, end));
	min = Math.min(min, res);
	}
	table[start][end] = min;
	return min;
	}
	}

view raw LC 375. Guess Number Higher or Lower II - LeetCode Google DynamicProgramming MinMax.java hosted with ❤ by GitHub