本文主要是介绍poj 1243 One Person（dp，记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
有一个人在猜数字，总共有G次猜测机会，L次猜高的机会。问他能够猜对的最大数字是什么。
如果猜错，那么G-1，如果是猜高了，那么需要额外L-1，当猜对或者G<0或者L<0的时候，猜测结束。
一开始把题目理解成：猜低，G-1，猜高L-1，G变为初始值。但是样例都不过掉。
解题思路：
根据正确的题意，那么我们可以很容易想到一个状态转移方程：dp[i][j] = dp[i-1][j-1]+dp[i-1][j] 其中i表示剩余的猜测次数，j表示剩余的生命线。
这边，我用了记忆化搜索的方式来计算具体的dp值。当L>G时，多余的L其实是浪费的，当L=0时，最优的策略就是一个一个的往上猜，所以dp[i][0] = i;
代码如下：
#include<cstdio>
#include<cstring>
using namespace std;
bool vis[55][55];
int dp[55][55];
int DP(int x,int y)
{if(y>x)y = x;if(vis[x][y])return dp[x][y];vis[x][y]=true;if(y==0)return dp[x][y]=x;return dp[x][y]=DP(x-1,y-1)+DP(x-1,y)+1;
}
int main()
{int n,m,i,j,ca=1;while(scanf("%d%d",&n,&m)==2){if(n==0&&m==0)break;memset(vis,0,sizeof(vis));printf("Case %d: %d\n",ca++,DP(n,m));}return 0;
}
这篇关于poj 1243 One Person（dp，记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
