G-L6挂经

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

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

lllxin37 发表于 2021-5-27 06:44
请问左到右，右到左咋work？ 需要三维dp么?

[#, #, O, #]

面试官说可以三维，也可以不用，我也是纠结在右到左的话rule，最后没搞定

lllxin37 发表于 2021-5-27 06:44
请问左到右，右到左咋work？ 需要三维dp么?

[#, #, O, #]

对于每一层，用两个array分别记录从左往右和从右往左（同时记录一下从上往下，这个没啥），然后合并

面L6还出DP，面试官脑袋有坑

patriotJ 发表于 2021-5-27 07:19
对于每一层，用两个array分别记录从左往右和从右往左（同时记录一下从上往下，这个没啥），然后合并

我来试试

二院老同志 发表于 2021-5-27 07:30
面L6还出DP，面试官脑袋有坑

而且是咱自己人呢

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

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

zhangjian800 发表于 2021-5-27 07:06
面试官说可以三维，也可以不用，我也是纠结在右到左的话rule，最后没搞定

可以不用三维DP， 因为我们只关心last row, 所以可以缩减为2维度的。

上面写的三维DP rule可以变成这个:

1. 
   
2. 
   
3. oneRow[n][3]
   
4. newRow[n][3]
   
5. 
   
6. newRow[j][2] = max(oneRow[j][0], oneRow[j][1], oneRow[j][2]) // from top
   
7. newRow[j][0] = max(newRow[j-1][0], newRow[j-1][2]) // left to right
   
8. newRow[j][1] = max(newRow[j+1][1], newRow[j+1][2])  // right to left
   
9. 
   
10. 实现时候可以把from top和from left写在一起

复制代码

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

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

感觉考官估计直接想要bottom to top的答案吧 这道题top to bottom好像还可以想得到 三维数组就行。。希望面试官不要这么变态