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)/2low = 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 = 22n=9,5+7+8=20输入:109输出:1614用动态规划来做：关键: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，就可以说明猜正确，最后一次耗费0int 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;}