GOOGLE ONSITE一道最近高频DP

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

给你个提示吧，状态转移方程是 S[i][j][k] i代表第i天，j代表可以有j天的absence，k代表最后j天连续late，之后的你想想就很容易写出来了

感觉就是个sliding window题目，非要用DP的话我估计要三维DP

pwwpche 发表于 2017-2-14 02:02
dp方程看起来复杂，但是时间复杂度是O(n), 因为n的状态只跟n-1时状态有关，所以完全可以优化成空间复杂度 ...

> backtrack的时间复杂度O(n^2)
这个复杂度是怎么算的？我觉得backtracking很慢啊

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ryuichist 发表于 2017-2-14 09:10
感觉就是个sliding window题目，非要用DP的话我估计要三维DP

握爪　　我也觉得是sliding window...

1. int reward_string_cnt(int n){
   
2.     if(n == 1)
   
3.         return 3;
   
4.     if(n == 2)
   
5.         return 8;
   
6.     vector<vector<vector<int>>> f(n, vector<vector<int>>(2, vector<int>(3)));
   
7. 
   
8.     f[2][0][0] = 4;  
   
9.     f[2][0][1] = 2;
   
10.     f[2][0][2] = 1;
    
11.     f[2][1][0] = 8;
    
12.     f[2][1][1] = 3;
    
13.     f[2][1][2] = 1;
    
14. 
    
15.         
    
16.     for(int i=3; i<n; i++){
    
17.         //no L in tail
    
18.         //  
    
19.         //without A
    
20.         f[i][0][0] = f[i-1][0][1] + f[i-1][0][2];
    
21.             
    
22.         //with A
    
23.         f[i][1][0] = f[i-1][1][0] + f[i-1][1][1] + f[i-1][1][2] + //with O tail
    
24.                     f[i-1][0][0] + f[i-1][0][1] + f[i-1][0][2]; //with A tail
    
25. 
    
26.         //L in tail
    
27.         //  
    
28.         //with 1 L tail, without A
    
29.         f[i][0][1] = f[i-1][0][0];
    
30.         //with 1 L tail, with A
    
31.         f[i][1][1] = f[i-1][1][0];
    
32.         //with 2 L tail, without A
    
33.         f[i][0][2] = f[i-1][0][1];
    
34.         //with 2 L tail, with A
    
35.         f[i][1][2] = f[i-1][1][1];
    
36.     }   
    
37. 
    
38.     int cnt = 0;
    
39.     for(int j=0;j<2;j++){
    
40.         for(int k=0;k<3;k++){
    
41.             cnt += f[n-1][j][k];
    
42.         }
    
43.     }
    
44. 
    
45.     return cnt;
    
46. }

复制代码

随手写的，不知道对不对.

18844549105 发表于 2017-2-14 17:24
随手写的，不知道对不对.

好像不对，n=4的时候比我DFS的少几种，我看了一下找出来的集合并没有不合法的。

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies