# 说道谷歌的 onsite 题目letter 选择

n 个位置，即 1，2，…，n

1 Like

dp该怎么解？

dp[i][j] 代表 前 i 个位置一共用了 j 种字母。
dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]

1 Like

————— 2019-01-29 —————

king~蛙 00:07

Shawn Dong 00:07

X 00:08

X 00:08

X 00:08

X 00:08

i是什么，神仙知道

king~蛙 00:08

king~蛙 00:08

X 00:09

king~蛙 00:09

[捂脸]

X 00:11

X 00:11

X 00:11

Shawn Dong 00:11

Shawn Dong 00:12

X 00:12

Shawn Dong 00:12

oyashiroshama 00:12

dp[4]的值不对吧。。

Shawn Dong 00:12

X 00:13

dp对不对自己就能测吧

X 00:13

n可以很大

Shawn Dong 00:13

Shawn Dong 00:13

n 能做 1e18 的

X 00:14

1e18有什么特殊含义吗

Shawn Dong 00:14

long 的最大值

X 00:14

[机智]

Shawn Dong 00:14

king~蛙 00:14

X 00:15

X 00:15

X 00:15

X 00:15

n这里说了是n个位置

king~蛙 00:15

X 00:16

Shawn Dong 00:16

dp[i][j] 代表 前 i 个位置一共用了 j 种字母。
dp[i][j] = (dp[i - 1][j] dp[i - 1][j - 1]) * j

X 00:16

X 00:17

Shawn Dong 00:17

dp[i][j] 代表 前 i 个位置一共用了 j 种字母

Shawn Dong 00:18

Shawn Dong 00:18

Shawn Dong 00:18

。。。抱歉写错了 2333

Shawn Dong 00:18

dp[i][j] = dp[i - 1][j] * j dp[i - 1][j - 1]

Shawn Dong 00:19

Shawn Dong 00:19

X 00:20

Shawn Dong 00:20

king~蛙 00:20

X 00:21

X 00:21

X 00:21

[机智]

Shawn Dong 00:22

X 00:22

[表情]

Shawn Dong 00:22

X 00:22

X 00:22

X 00:22

Shawn Dong 00:24

Shawn Dong 00:24

X 00:24

Shawn Dong 00:24

X 00:24

Shawn Dong 00:24

Shawn Dong 00:24

X 00:25

Shawn Dong 00:25

X 00:25

Shawn Dong 00:26

T——T

Shawn Dong 00:26

X 00:26

Shawn Dong 00:26

Shawn Dong 00:26

Shawn Dong 00:26

Shawn Dong 00:26

Shawn Dong 00:27

X 00:27

Shawn Dong 00:27

X 00:27

X 00:28

X 00:28

X 00:29

Shawn Dong 00:29

lol

X 00:29

X 00:29

X 00:29

X 00:29

X 00:30

``````#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int dp[2][27] , n;
int main(){
cin >> n;
memset(dp , 0 , sizeof(dp));
dp[0][1] = 1;
int last = 0;
for (int i = 1 , u = 0 , v = 1 ; i < n ; i ++ , swap(u , v)){
memset(dp[v] , 0 , sizeof(dp[v]));
for (int j = 1 ; j <= 26 ; ++j) if (dp[u][j]){
dp[v][j] += j * dp[u][j];
if (j < 26) dp[v][j + 1] += dp[u][j];
}
last = v;
}
int ans = 0;
for (int i = 1 ; i <= 26 ; ++i)
ans += dp[last][i];
cout << ans << endl;
return 0;
}
``````
2 Likes

@Shawn_Dong 是对的，你再理解理解