[CareerCup][Google Interview] 打印最长序列

发布于:2021-10-26 04:04:42

1. A

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.


So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).


?


这题又是一道经典的DP。打印这种类似最大结果的问题一般都会想到用DP


f[i][4]: 表示有四种方法,f[i][j] = max(f[i-1][k] + 各种操作)


如果要打印每个操作步骤,则要再设一个parent[i][j]数组,记录他的前任操作是哪个,然后递归调用。



1 #include
2 using namespace std;
3
4 int solve(int n)
5 {
6 int f[100][4];
7
8 memset(f, 0, sizeof(f));
9
10 f[0][0] = 1;
11
12 for(int i = 1; i < n; i++)
13 for(int j = 0; j < 4; j++)
14 for(int k = 0; k < 4; k++)
15 {
16 if (j == 0) // add A
17 {
18 f[i][j] = max(f[i][j], f[i-1][k] + 1);
19 }
20 else if (j == 1) // ctrl+A
21 {
22 f[i][j] = max(f[i][j], f[i-1][k]);
23 }
24 else if (j == 2) // ctrl+C
25 {
26 if (k == 1) // only previous is ctrl+A makes ctrl+C available
27 f[i][j] = max(f[i][j], f[i-1][k]);
28 }
29 else if (j == 3) //ctrl+V
30 {
31 if (k == 2)
32 f[i][j] = max(f[i][j], f[i-1][k] * 2);
33 }
34 }
35
36 return max(f[n-1][3], f[n-1][0]);
37 }
38
39 int main()
40 {
41 int N = 10;
42 cout << solve(N) << endl;
43 }






相关资源:cracking the coding interview第六版

相关推荐

最新更新

猜你喜欢