GOOGLE ONSITE一道最近高频DP

caseinter

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

L代表late，A代表absence，O代表正常出席，input是一个string，包含L，A，O，要求不能

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

量. more info o

这题DP谁能写写？

codepike

int count(int n) {
// igore "A" first, and consider "O" and "L" only
// create a 2D array dp[i][j]
// dp[i][0] the number of rewardable string with length of i and the last letter is "O"
// dp[i][1] the number of rewardable string with length of i and the last letter is "L"
vector<vector<int>> dp(n+1, vector<int>{1,0});
dp[1] = {1,1};
for (auto i = 2; i <= n; ++i) {
dp[i][0] = dp[i-1][0] + dp[i-1][1]; // the ith letter is O
dp[i][1] = dp[i-1][0] + dp[i-2][0]; // the ith letter is L
}
int res = dp[n][0] + dp[n][1]; // case when there is no "A"
// consider all the cases with one A
// there are i letters to the left of A and n-i-1 letter to the right of A
for (int i = 0; i < n; ++i) {
res += (dp[i][0]+dp[i][1])*(dp[n-i-1][0] + dp[n-i-1][1]);
}
return res;
}

复制代码

kqxqx

李特口德唔唔耳

csehao

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

lhh_NJU

Followup 没看懂. 但是就题目本身而言, 为啥要用DP啊? 一遍扫过去不就可以了吗?

4seasonoffer

lhh_NJU 发表于 2017-2-13 08:25
Followup 没看懂. 但是就题目本身而言, 为啥要用DP啊? 一遍扫过去不就可以了吗?

follow up 要用dp
題意是要你找出所有長度為n 且會被award的出席狀況

say543

follow up 不能maintain 一个window 像sliding window 一样来check 有没有3 consecutive late吗?

AndrewFish

DFS +BT不就行了？

AndrewFish

DP的话看看最后几个是不是都是late 然后absence用过没分情况讨论？

dexter

谢谢楼主分享！想一想这题

pwwpche

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Mr.Sagemaker

follow up 只要求返回数量的话，这样解不行咩？长度为n的string总数量再减去 un-rewardable的string 数量;

cgxy1991

第二问用dp恐怕太过复杂，用backtracking解吧。。。