（算法）猜数字⼤⼩II————＜暴搜-＞记忆化搜索-＞动态规划＞

1. 题⽬链接：375.猜数字⼤⼩II

2. 题⽬描述：

3. 解法（暴搜->记忆化搜索）：

算法思路：

暴搜：

a. 递归含义：给dfs ⼀个使命，给他⼀个区间[left, right] ，返回在这个区间上能完胜 的最⼩费⽤； b. 函数体：选择[left, right] 区间上的任意⼀个数作为头结点，然后递归分析左右⼦树。 求出所有情况下的最⼩值；

c. 递归出⼝：当left >= right 的时候，直接返回0 。

记忆化搜索：

a. 加上⼀个备忘录；

b. 每次进⼊递归的时候，去备忘录⾥⾯看看；

c. 每次返回的时候，将结果加⼊到备忘录⾥⾯。 

C++算法代码： 

class Solution 
{
public:
    int dp[201][201];
    //返回以该位置为头结点所需的金额
    int dfs(int left,int right)
    {
        if(left>=right)
        {
            return 0;
        }
        if(dp[left][right])
        {
            return dp[left][right];
        }
        dp[left][right]=INT_MAX;
        //选择头结点
        for(int head=left;head<=right;head++)
        {
            //左节点
            int x=dfs(left,head-1);
            //右节点
            int y=dfs(head+1,right);
            //取其中最大值，然后加上自身的值
            dp[left][right]=min(dp[left][right],head+max(x,y));
        }
        return dp[left][right];
    } 
    int getMoneyAmount(int n) 
    {
        return dfs(1,n);
    }
};

Java算法代码：

class Solution
{
	int[][] memo;
	public int getMoneyAmount(int n)
	{
		memo = new int[n + 1][n + 1];
		return dfs(1, n);
	}
	public int dfs(int left, int right)
	{
		if (left >= right) return 0;

		if (memo[left][right] != 0)
		{
			return memo[left][right];
		}
		int ret = Integer.MAX_VALUE;
		for (int head = left; head <= right; head++)
		{
			int x = dfs(left, head - 1);
			int y = dfs(head + 1, right);
			ret = Math.min(Math.max(x, y) + head, ret);
		}
		memo[left][right] = ret;
		return ret;
	}
}