今天的题目是375. Guess Number Higher or Lower II

一道动态规划问题,一开始以为是通过二分查找的方式来计算就好了,但是后面发现这样算出来答案不是最优的。

思路大概是这样的,把问题先泛化为,给定从ij的数字,猜数字的最大代价,为了得到最大代价,我们不妨假设每次都猜错,直到只有一个元素时。

第一次猜的时候,我们可以猜从ij的任意一个数字k,这时代价为k,猜错后可能得到两种回答,比k大或者比k小,这时我们的问题转换为两个子问题:

  • 给定ik-1的数字,猜数字的最大代价
  • 给定k+1j的数字,猜数字的最大代价

ij的数字的数目小于等于1时,代价为0

据此,我们可以写出以下动态规划方程:

dp[i,j]={0,(ji+1)>=0mini<=k<=j{dp[i,k1]+k+dp[k+1,j]},othersdp[i,j] = \left\{ \begin{aligned} 0 & , & (j - i + 1) >= 0 \\ min_{i<=k<=j}\{dp[i,k-1] + k + dp[k+1,j]\} & , & others \end{aligned} \right.

由于计算dp[i,j]需要dp[i,k-1]dp[k+1,j],所以我们可以直到它是沿着斜对角线计算得到dp[1,n]的,如下图所示:

guess-number-higher-or-lower-ii-20201009202433-2020-10-09

因此,我们可以根据动态规划方程写出如下代码:

int getMoneyAmount(int n) {
	vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
	for (int step = 1;step < n;step++) {
		for(int i = 1,j = 1 + step;j <= n;i++,j++) {
			// int j = i + step;
			// if (j > n) break;
			// dp[i][j] = INT_MAX;
			dp[i][j] = dp[i][j-1] + j;
			for(int k = i;k < j;k++) {
				dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]));
			}
		}
	}
	return dp[1][n];
}

作者:wuxiaobai24

发表日期:10/9/2020

本文首发地址:375. Guess Number Higher or Lower II

版权声明:CC BY NC SA 4.0

本站总访问量次 本站访客数人次

Design by wuxiaobai24. Power by Gatsby.js. The website content is licensed CC BY NC SA 4.0.

You can find the source code in Github.