leecode 解题总结：3383. Ransom Note

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
/*
问题:
We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

分析：明显得，如果把答案设置在为n，采用二分法需要获取的代价是最多的。
假设n=10,最终选取的也是10，
刚开始
low = 1 , high=10 , mid=(1+10)/2=5,付出5  , (low + high)/2
low = 6 , high=10 , mid=8,    ( (low+high)/2 + 1 + high ) / 2 = 3/4 * high + 1/4 * low + 1/2 
low = 9 , high=10, mid=9 ，
low = 10, high=10 , mid=10,猜中
总共花费=5 + 8 + 9 = 22
n=9,
5+7+8=20

输入:
10
9
输出:
16
14

用动态规划来做：
关键:
1 
参考：http://blog.csdn.net/adfsss/article/details/51951658
设任意猜一个数为i,保证获胜说花的钱：
i + max( dp(1,i-1) , dp(i+1,n) )
这里dp(x,y)表示猜范围在(x,y)的数保证能赢应花的钱
遍历1~n作为猜的数，求出其中的最小值就是答案。

2
//递归计算，因为要保证赢，我们一直假设当前猜数i是猜错的，然后一直到最后start >= end，就可以说明猜正确，最后一次耗费0
int temp = i + max( cost(dp , start , i - 1 ) , cost(dp , i+1 , end) );
//对于每个初始猜数i，计算其最多需要多少钱才能猜正确，然后从里面选择一个初始猜数最小的即可
result = min(temp , result);

dp.at(start).at(end) = result;//记录最终结果，便于记忆化搜索
*/

class Solution {
public:
	int cost(vector< vector<int> >& dp , int start , int end)
	{
		if(dp.empty() ||start < 0 || end >= dp.size() || start >= end)
		{
			return 0;
		}
		if(dp.at(start).at(end) != 0)
		{
			return dp.at(start).at(end);
		}
		int result = INT_MAX;
		for(int i = start ; i <= end ; i++)
		{
			//递归计算，因为要保证赢，我们一直假设当前猜数i是猜错的，然后一直到最后start >= end，就可以说明猜正确，最后一次耗费0
			int temp = i + max( cost(dp , start , i - 1 ) , cost(dp , i+1 , end) );
			//对于每个初始猜数i，计算其最多需要多少钱才能猜正确，然后从里面选择一个初始猜数最小的即可
			result = min(temp , result);
		}
		dp.at(start).at(end) = result;//记录最终结果，便于记忆化搜索
		return result;
	}

    int getMoneyAmount(int n) {
		vector< vector<int> > dp(n + 1 , vector<int>(n+1 , 0));
		int result = cost(dp , 1 , n);
		return result;
	}
};


void process()
{
	 int num;
	 Solution solution;
	 while(cin >> num )
	 {
		 int result = solution.getMoneyAmount(num);
		 cout << result << endl;
	 }
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}