美团校招算法题 抽牌 动态规划

问题描述：桌上有n张牌，编号为1到n，每张牌上有一个数字，第i张牌的数字为，现在小方和小明两个人玩游戏，轮流抽牌，每人一次只能抽一张牌，小明先抽。每次抽牌只能抽取最上面的牌或者最下面的牌，他们两个都是随机抽取，小明每次抽取上面的牌的概率为p，抽取下面的牌的概率为1-p。小方每次抽取上面的牌的概率为q，抽取下面的概率为1-q。最后他们的得分为所有牌上的数字之和，求小明的分数期望。

输入描述：第一行为三个数， , 第二行为n个数，为每张牌上的分数。

解题思路：首先应该想到这个题的暴力解法，小方和小明每次都有两种抽取的方法，每一种方法小明都可以得到一个分数，然后将这些分数和概率相乘，然后把所有的结果相加就能得到小明分数的期望，时间复杂度为指数级，代码如下：

#include<iostream>
#include<vector>
using namespace std;
float fb(vector<int> arr, int i, int j, float p, float q, float p_all, int m){
if(i == j){
return (m + arr[i])*p_all;
}
if(i == j - 1){
return (m + arr[i]) * p * p_all + (m + arr[j]) * (1 - p) * p_all;
}
return fb(arr, i + 2, j, p, q, p_all * p * q, m + arr[i]) +
fb(arr, i + 1, j - 1, p, q, p_all * p * (1 - q), m + arr[i]) +
fb(arr, i, j - 2, p, q, p_all * (1 - p) * (1 - q), m + arr[j]) +
fb(arr, i + 1, j - 1, p, q, p_all * (1 - p) * q, m + arr[j]);
}
int main(){
int n;
int a;
int b;
while(cin >> n >> a >> b){
float p = a / 100.0;
float q = b / 100.0;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
printf("%.3f",
fb(arr, 0, n - 1, p, q, 1, 0));
}
return 0;
}

但是，这种方法时间复杂度太高，不能AC，只能解决40%的数据。但是，有一点刷题经验的人都知道这种指数级别的时间复杂度，大部分都能够通过动态规划的方法来解决，这个题也一样。我们用dp[i][j]表示从i到j这些数小明能够获得的得分期望，我们可以得到递推公式：

这里的arr[i]为第i张牌的数字。代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
int a;
int b;
while(cin >> n >> a >> b){
double p = a / 100.0;
double q = b / 100.0;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
vector<vector<double>> dp(n, vector<double>(n, 0));
for(int i = 0; i < n; i++){
dp[i][i] = arr[i];
if(i < n - 1){
dp[i][i + 1] = p * arr[i] + (1 - p) * arr[i + 1];
}
}
for(int l = 2; l <= n - 1; l++){
for(int i = 0; i < n - l; i++){
int j = i + l;
dp[i][j] = p*(q * dp[i + 2][j] + (1 - q) * dp[i + 1][j - 1] + arr[i])
+ (1 - p)*(q * dp[i + 1][j - 1] + (1 - q) * dp[i][j - 2] +arr[j]);
}
}
printf("%.3f", dp[0][n - 1]);
}
return 0;
}

时间复杂度为，注意要用double，用float有一些数据通不过。

最后

以上就是体贴雪糕为你收集整理的美团校招算法题 抽牌 动态规划的全部内容，希望文章能够帮你解决美团校招算法题 抽牌 动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。