GOOGLE ONSITE一道最近高频DP

csehao 发表于 2017-2-27 15:01
感觉不需要3唯DP吧, 因为不需要考虑O, 正常出席, int[][] DP = new int[3][2]; 第一维以当前为结尾, 已经连 ...

同意。可以创建两个二维数组。一个存i-1的状态，另一个存当前的，最后把当前的赋值给i-1。

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

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

codepike 发表于 2017-3-17 10:13

太聪明了！先不考虑'A'

Java version

1. public class RewardStudent {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         System.out.println(count(4));
   
5.     }
   
6. 
   
7.     public static int count(int n) {
   
8.         int[][] dp = new int[n + 1][2];
   
9.         dp[1][0] = 1;
   
10.         dp[1][1] = 1;
    
11.         for (int i = 2; i <= n; i++) {
    
12.             dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
    
13.             if (i == 2) {
    
14.                 dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
    
15.             } else {
    
16.                 dp[i][1] = dp[i - 1][0] + dp[i - 2][0];
    
17.             }
    
18.         }
    
19. 
    
20.         int res = dp[n][0] + dp[n][1];
    
21.         for (int i = 0; i < n; i++) {
    
22.             res += (dp[i][0] + dp[i][1]) * (dp[n - i - 1][0] + dp[n - i - 1][1]);
    
23.         }
    
24. 
    
25.         return res;
    
26.     }
    
27. }

复制代码

1. '''
   
2. dp[i][0] stands for # of string whose length is i ends with O
   
3. dp[i][1] stands for # of string whose length is i ends with A
   
4. dp[i][2] stands for # of string whose length is i ends with L
   
5. '''
   
6. 
   
7. def numOfRewardable(self, n):
   
8.         dp = [[0, 0, 0] for i in range(max(4, n + 1))]
   
9.         dp[1] = [1, 1, 1]
   
10.         dp[2] = [3, 2, 3]
    
11.         dp[3] = [7, 4, 8]
    
12. 
    
13.         for i in range(4, n + 1):
    
14.             dp[i][2] = sum(dp[i - 1])
    
15.             # ends up with O
    
16.             dp[i][1] = dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]
    
17.             # ends up with A
    
18.             # replace M[i-1][1]'s last A with O
    
19.             # replace M[i-2][1]'s last A with O and insert L after that
    
20.             # replace M[i-3][1]'s last A with O and insert LL after that
    
21.             dp[i][0] = dp[i][2] - (dp[i - 3][1] + dp[i - 3][2])
    
22.             # ends up with L
    
23.             # ___ALL + L and ___OLL + L cases that cause invalid string have been counted
    
24.             # in M[i][2] (i.e sum(M[i-1]))
    
25.             # then drop them by reducing M[i-3][1] + M[i-3][2]
    
26.             # note that LLL + L won't be counted in M[i][2] because of LLL is already illegal
    
27.         return sum(dp[n])

复制代码

我的代码，经测试和DFS结果一致。

这题用DP感觉毫无意义

李特口德 唔唔耳

kqxqx 发表于 2017-10-9 05:20
李特口德 唔唔耳

寒假的时候lc只有490题。。哈哈