求问一道DP 题目

今天早上面了一个中小型startup的 onsite的两轮coding，其中有一道dp题不会做，刷题网也没怎么搜到类似的题目，想请教一下地里的大神们。
题目内容很简单，就是给一个二维矩阵，每一格里面的数值可以是0，1，2，3
0 表示这个房间可以进去，但是只能访问一次
1 表示这个房间不能进去
2 是起点，3 是终点。
矩阵只会有一个起点和一个终点，只不过可以在任意位置。
求问，从起点出发，要走遍所有是0的格子，最后走到终点，问有多少种不同的路径。

例子：
输入是：
2，0，0，0
0，0，0，0
0，0，3，1

返回是2，因为一共有两条路径可以走，所经过的坐标分别是：
1：(0,0) -> (0,1) -> (0,2) -> (0,3) ->

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

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

(1,2) -> (2,2)

我写了个dfs 的暴力解法，但是感觉这不是面试官真正想要的答案，面试官应该想要的是bottom up dp解法。求问地里的大神们，这题用dp咋做？

WLBjob7344 发表于 2021-6-30 13:47
樓主，你是最近去這家公司面試的人了，能告訴我一下你的面經嗎？ 感謝了

具体题目有点记不清了，电面+onsite一共面了，2道DP，包括这道，1道BFS, 还有一道比较繁琐的encode/decode的题，题目都不难，除了最后一题corner case比较多。从他们家的评分方式来看，并不需要最优解才能过，暴力解也能过，但是我猜可能影响最后的包裹大小。

WLBjob7344 发表于 2021-7-4 14:03
樓主，再請教你一個問題，我約了要電面，但他們發給我的是zoom link，你當時電面也是zoom和他們見面嗎？然 ...

我当时是电面的时候面试官会给我发hackerank的链接。如果有啥不清楚的，建议直接问hr

xxxxc 发表于 2021-7-1 02:33
具体题目有点记不清了，电面+onsite一共面了，2道DP，包括这道，1道BFS, 还有一道比较繁琐的encode/decod ...

謝謝樓主。這些題目都是咱們地裡出現過的原題嗎？

https://leetcode.com/problems/unique-paths-iii/

樓主，你是最近去這家公司面試的人了，能告訴我一下你的面經嗎？ 感謝了

WLBjob7344 发表于 2021-7-1 04:42
謝謝樓主。這些題目都是咱們地裡出現過的原題嗎？

这家公司我没怎么看地里的面经，主要是太少了

xxxxc 发表于 2021-7-1 06:54
这家公司我没怎么看地里的面经，主要是太少了

樓主，請問下你當時申請Lime，他們家有讓你做OA嗎？

WLBjob7344 发表于 2021-7-2 05:05
樓主，請問下你當時申請Lime，他們家有讓你做OA嗎？

没有，直接电面

xxxxc 发表于 2021-7-2 06:10
没有，直接电面

嗯嗯，謝謝

xxxxc 发表于 2021-7-2 06:10
没有，直接电面

請問你當時有拿到offer嗎？是面哪個崗位呢？