不一样的猜数字游戏 — leetcode 375. Guess Number Higher or Lower II
好久没切 leetcode 的题了，静下心来切了道，这道题比较有意思，和大家分享下。
我把它叫做 "不一样的猜数字游戏"，我们先来看看传统的猜数字游戏，Guess Number Higher or Lower。题意非常的简单，给定一个数字 n，系统会随机从 1 到 n 中抽取一个数字，你需要写一个函数 guessNumber，它的作用是返回系统选择的数字，同时你还有一个外部的 API 可以调用，是为 guess 函数，它会将你猜的数字和系统选择的数字比较，是大了还是小了。
非常的简单，稍微有点常识的童鞋应该都能想到二分查找的方案（插句题外话，这游戏让我想到了儿时的幸运52）。关于二分查找，可以参考下我以前写的一篇文章 http://www.cnblogs.com/zichi/p/5118032.html，几乎囊获了所有二分查找的情况。这道题代码比较简单，可以参考 guess-number-higher-or-lower.cpp，比较蛋疼的是不支持 JavaScript。
核心代码：
int guessNumber(int n) { int start = 1, end = n; int ans; while (start <= end) { int mid = start + (end - start) / 2; int val = guess(mid); if (val == -1) end = mid - 1; else if (val == 1) start = mid + 1; else { ans = mid; break; } } return ans;}还有一点需要注意下，取 mid 值时不能用 (start + end) / 2，不然会溢出，TLE 掉！
接着进入正题，来看 Guess Number Higher or Lower II 这道题，跟前者比，有何区别呢？同样是给定一个数字 n，系统会随机从 1 到 n 中选择一个整数，你要做的还是将这个数猜出来。你每猜一个数字，需要花费一定的 money，比如你猜 m，那么你就要花费 m，求解你要将这个数字猜出来，至少需要的 money。
举个栗子，比如 n 为 5，系统选择的数字是 1。如果我先猜 3，系统提示你猜大了，然后再猜 2，系统提示你猜大了，那么你就可以确定是 1 了，花费 3+2=5。但是很明显第二次猜测应该猜 1，这样花费就少了。再比如我选的是 4，第一次还是猜 3，系统提示你猜小了，第二次猜 4，中了，总共花费 3+4=7，如果 n 为 5，至少需要 7？非也，正确的解法是先猜 4，如果数字在 1-3 之间，那么再猜 2，至少需要的应该是 6！
这是一道很典型的动态规划题，你根本不可能去盲目地猜，然后使劲地暴力递归去解！这样的复杂度是指数级的。是否能够递推求解？比如已经知道 n 为 1-5 的情况，当 n 为 6 时，第一次猜，我们可以有 6 种猜法，分别选择 1,2,3,4,5 和 6，我们以猜 3 为例，比如说第一把猜了 3，那么如果猜的大了，那么我们接下去要求的是从 [1, 2] 中猜到正确数字所需要花费的最少 money，记为 x，如果猜的小了，那么我们接下去要求的是从 [4, 6] 中猜到正确数字所需要花费的最少 money，记为 y，如果刚好猜中，则结束。很显然，如果第一把猜 3，那么猜中数字至少需要花费的 money 为 3 + max(x, y, 0)，"至少需要的花费"，就要我们 "做最坏的打算，尽最大的努力"，即取最大值。这是第一把取 3 的情况，我们还需要考虑其他 5 种情况，然后六种情况再取个最小值，就是 n=6 至少需要的 money！（想想，是不是这样？）
最后来编码，我们需要一个二维数组来表示最值。首先我们定义一个二维数组 ans[][]，ans[i][j] 表示 i-j 中任取一个数字，猜中这个数字需要至少花费的 money。
定义 ans 数组，并且初始化：
// ans[i][j] 表示从 [i, j] 中任取一个数字// 猜中这个数字至少需要花费的 moneyvar ans = [];for (var i = 0; i <= n; i++) ans[i] = [];接着我们定义一个函数 DP，DP(ans, x, y) 表示 [x, y] 中任取一个数字，猜中这个数字需要花费的最少 money，而 ans 是为数组的引用。很显然，我们要求的就是 DP(ans, 1, n) 的返回值，直接看代码。
function DP(ans, from, to) { // 如果 from >= to if (from >= to) return 0; // 如果 ans[from][to] 已经求得 // 直接 return if (ans[from][to]) return ans[from][to]; // 先赋值 Infinity，便于之后的比较 ans[from][to] = Infinity; // 现在要从 [from, to] 中猜数字 // 假设先猜 i，i 可以是 [from, to] 中的任何数字，遍历之 for (var i = from; i <= to; i++) { // left 为从 [from, i - 1] 猜对数字至少需要花费的 money var left = DP(ans, from, i - 1); // right 为从 [i + 1, to] 猜对数字至少需要花费的 money var right = DP(ans, i + 1, to); // tmp 为先猜 i，从 [from, to] 猜对数字至少需要花费的 money var tmp = i + Math.max(left, right); // 跟别的方案比较（即跟不是先猜 i 的方法比较） // 取最小值 ans[from][to] = Math.min(ans[from][to], tmp); } return ans[from][to];}注释写的很清晰了，如果再细分的话，个人觉得这可以说是一道 "记忆化DP"，不晓得有没有这个词？好像只听说过 "记忆化搜索"？DP 本来就是记忆化的过程吧？好了不钻牛角尖了，完整代码可以从我们的 Repo https://github.com/hanzichi/leetcode 获取。
