n 个位置，即 1，2，…，n
从左往右开始往里面放letter，letter的选择规则是，要么从已经出现过的letter里选，要么就是一个新的letter
位置1: 只能是A
位置2: A 或 B
位置3: 如果你在位置2选了A，那么选择是A或B。如果你在位置2选了B，那么你可以选 A，B或C。
以此类推。
求n个位置，有多少种不同的String
如果是C后面跟什么
这不是非常基础的矩阵优化的动态规划么
如果是C，说明A，B，C已经出现过了，那么你有四个选择，多了一个D
dp该怎么解？
可以认为字母数字上限是个常数，比如26。但解题时候这个是个input
最基本的解法是：
dp[i][j] 代表 前 i 个位置一共用了 j 种字母。
dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]
如果就 26 个字母的话，那么可以用矩阵优化
复杂度可以做到 26 * 26 * 26 * log(n)
1 个赞
目测是对的，你说的矩阵优化是指把二维矩阵降成一维吗？
还是二维，但是能用矩阵乘法快速幂降低n的计算复杂度
不是为了优化空间？
是优化runtime对吗？
对的，用空间换时间。
谷歌letter 选择题 微信群上的聊天记录如下，请查收。
————— 2019-01-29 —————
king~蛙 00:07
老师 是不是dp[i] = dp[i-1]*(i-1) (i 1) 啊？
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
是最多有26个字母么
Shawn Dong 00:12
还是有无限多个字母？
X 00:12
可以认为字母上线是个常数，比如26。但解题时候这个是给input
Shawn Dong 00:12
哦
oyashiroshama 00:12
dp[4]的值不对吧。。
Shawn Dong 00:12
那 n 能做 1e18 的
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
当然如果有足够多的可以做2^1000 级别的
king~蛙 00:14
我觉得 就是 当前选择的时候 有n-1种可能是选择之前已经出现过的 那就乘以上一个level的dp值 然后新出现的字母 又可以有n种新的可能
X 00:15
别用n了吧
X 00:15
很困惑
X 00:15
换成k啊啥的
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
如果就 26 个字母的话，那么可以用矩阵优化
复杂度可以做到 262626*log(n)
X 00:16
面试很负面的
X 00:17
这个递推可以解释一下吗？看上去是得用二维dp
Shawn Dong 00:17
dp[i][j] 代表 前 i 个位置一共用了 j 种字母
Shawn Dong 00:18
要么前 i - 1 的位置已经一共用了 j 种
Shawn Dong 00:18
要么 i - 1 的位置用了 j - 1 种
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
如果用了 j 种想转移到 dp[i][j] 的那么随便取一个
Shawn Dong 00:19
如果用了 j - 1 种想转移到 j 的只能是新的哪一个
X 00:20
目测是对的
Shawn Dong 00:20
所以复杂度要么是 26 * n 要么是 26^3*log(n)
king~蛙 00:20
好厉害
X 00:21
这思路应该是正解
X 00:21
然后就是写代码了
X 00:21
[机智]
Shawn Dong 00:22
我写个26^3*log(n)得把
X 00:22
[表情]
Shawn Dong 00:22
确定是 26 个字母哈
X 00:22
对
X 00:22
其实下一问就是26个字母
X 00:22
相当于followup
Shawn Dong 00:24
答案能对某个数取Mod 么。。。
Shawn Dong 00:24
否则可能存不下。。
X 00:24
你是怕太大？
Shawn Dong 00:24
是啊
X 00:24
这又不是leetcode
Shawn Dong 00:24
这是爆炸式增长的
Shawn Dong 00:24
哦好的
X 00:25
测n也不需要很大数
Shawn Dong 00:25
那26^3*log(n)的就没用了 TT 难受
X 00:25
你那个矩阵优化太高级了吧
Shawn Dong 00:26
T——T
Shawn Dong 00:26
好吧
X 00:26
但是写程序用的着这种数学吗？毕竟乘法开销大吧
Shawn Dong 00:26
看你怎么想了
Shawn Dong 00:26
如果n 真的很大
Shawn Dong 00:26
那么的确要用这个优化就是了
Shawn Dong 00:26
比如 n 是 1e9 级别的
Shawn Dong 00:27
你不能写个 26*n 的吧
X 00:27
我好像不太见到面试会这么操作。不过这么做的，想到这个的，我肯定给strong了
Shawn Dong 00:27
那我还是写个26n最省空间的吧
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 个赞
这个好像不对吧，还得加上dp[i-1][j-2]+dp[i-1][j-3]+…
@Shawn_Dong 是对的，你再理解理解
我拿ABCD试了一下，dp[4][3]会漏dp[3][1]这个解，也就是AAA
是么？我得再看看
我想了想，我可能理解错他这里dp的含义了。他这里dp[4][3]应该是指由3种不同字母组成的4位letter，也就是必须包括ABC。那样是对的。最后结果应该返回dp[n][1]+…+dp[n][26]
嗯是这个意思
可以加你微信嗎？最近刷題，想要請教一些方法
有问题在论坛发帖问好了，不用私信，也不欢迎私信询问。我不是做私人辅导的。