这一题如何DP做？# JobHunting - 待字闺中
j*d
1 楼
给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
方向的人，耗时1天。
问用多少天可以把所有可以被感染的1都感染成2.
我写的BFS，很简单的。请问这一题如何DP来做呢？
方向的人，耗时1天。
问用多少天可以把所有可以被感染的1都感染成2.
我写的BFS，很简单的。请问这一题如何DP来做呢？
j*o
2 楼
LC 994, 用DP反而麻烦吧
j*d
3 楼
如何dp，我真是没想出来。
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
j*d
4 楼
我悬赏50伪币，这一题DP来做。
j*d
5 楼
你用dp写出来了么？
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
【在 j******o 的大作中提到】
: LC 994, 用DP反而麻烦吧
l*r
6 楼
试一下这个
DP[i][j][t]是t次迭代之后position i，j被感染需要的天数
最后return max(DP[i][j][m*n] where M[i][j] = 1, m = len(M), n = len(M[0])
那
DP[i][j][t] = 1 + min_{x,y where M[x][y] != 0 and x,y is neighbor of i, j}
DP[x][y][t - 1]
初始条件DP[i][j][t] = 0 if M[i][j] = 2 else DP[i][j][t] = infinity
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
DP[i][j][t]是t次迭代之后position i，j被感染需要的天数
最后return max(DP[i][j][m*n] where M[i][j] = 1, m = len(M), n = len(M[0])
那
DP[i][j][t] = 1 + min_{x,y where M[x][y] != 0 and x,y is neighbor of i, j}
DP[x][y][t - 1]
初始条件DP[i][j][t] = 0 if M[i][j] = 2 else DP[i][j][t] = infinity
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
l*r
7 楼
这是code
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
in range(m)]
for i in range(m):
for j in range(n):
for t in range(m*n):
if grid[i][j] == 2:
DP[i][j][t] = 0
else:
DP[i][j][t] = float('inf')
for t in range(1, m*n):
for i in range(m):
for j in range(n):
if i + 1 < m and grid[i + 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i + 1][j][t -
1])
if i - 1 >= 0 and grid[i - 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i - 1][j][t -
1])
if j + 1 < n and grid[i][j + 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j + 1][t -
1])
if j - 1 >= 0 and grid[i][j - 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j - 1][t -
1])
res = -float('inf')
noOnesFlag = True
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and DP[i][j][m*n - 1] > res:
res = DP[i][j][m*n - 1]
noOnesFlag = False
if noOnesFlag == True:
return 0
return res if res < float('inf') else -1
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
in range(m)]
for i in range(m):
for j in range(n):
for t in range(m*n):
if grid[i][j] == 2:
DP[i][j][t] = 0
else:
DP[i][j][t] = float('inf')
for t in range(1, m*n):
for i in range(m):
for j in range(n):
if i + 1 < m and grid[i + 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i + 1][j][t -
1])
if i - 1 >= 0 and grid[i - 1][j] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i - 1][j][t -
1])
if j + 1 < n and grid[i][j + 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j + 1][t -
1])
if j - 1 >= 0 and grid[i][j - 1] != 0:
DP[i][j][t] = min(DP[i][j][t], 1 + DP[i][j - 1][t -
1])
res = -float('inf')
noOnesFlag = True
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and DP[i][j][m*n - 1] > res:
res = DP[i][j][m*n - 1]
noOnesFlag = False
if noOnesFlag == True:
return 0
return res if res < float('inf') else -1
【在 j*****d 的大作中提到】
: 你用dp写出来了么？
g*y
8 楼
把所有的感染者放入一个队列，每天就是把新感染的人放入一个新队列，等到新队列里
面没人了就是最后一天。
这样就可以O（n) n是所有的非0格子。
：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
：方向的人，耗时1天。
面没人了就是最后一天。
这样就可以O（n) n是所有的非0格子。
：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
：方向的人，耗时1天。
C*y
9 楼
日了，都994了。fk
LC提高了找工成本。
LC提高了找工成本。
d*w
10 楼
你这是BFS，他要DP。
4个
【在 g****y 的大作中提到】
: 把所有的感染者放入一个队列，每天就是把新感染的人放入一个新队列，等到新队列里
: 面没人了就是最后一天。
: 这样就可以O（n) n是所有的非0格子。
:
: ：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
: ：方向的人，耗时1天。
4个
【在 g****y 的大作中提到】
: 把所有的感染者放入一个队列，每天就是把新感染的人放入一个新队列，等到新队列里
: 面没人了就是最后一天。
: 这样就可以O（n) n是所有的非0格子。
:
: ：给一个matrix，0表示没有人，1表示健康的人，2表示受感染的人。2可以感染周围4个
: ：方向的人，耗时1天。
p*r
11 楼
好评！我想了一会儿就放弃了，
并且心中有一万只草泥马跑过，这不吃饱了撑了。
【在 l******r 的大作中提到】
: 这是code
: class Solution:
: def orangesRotting(self, grid: List[List[int]]) -> int:
: m = len(grid)
: n = len(grid[0])
: DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
: in range(m)]
: for i in range(m):
: for j in range(n):
: for t in range(m*n):
并且心中有一万只草泥马跑过，这不吃饱了撑了。
【在 l******r 的大作中提到】
: 这是code
: class Solution:
: def orangesRotting(self, grid: List[List[int]]) -> int:
: m = len(grid)
: n = len(grid[0])
: DP = [[[float('inf') for k in range(m*n)] for j in range(n)] for i
: in range(m)]
: for i in range(m):
: for j in range(n):
: for t in range(m*n):
j*d
12 楼
我给你看看他给我的feedback，你就知道什么叫天竺威武了。
【在 p**r 的大作中提到】
: 好评！我想了一会儿就放弃了，
: 并且心中有一万只草泥马跑过，这不吃饱了撑了。
【在 p**r 的大作中提到】
: 好评！我想了一会儿就放弃了，
: 并且心中有一万只草泥马跑过，这不吃饱了撑了。
l*r
13 楼
50 伪币呢？
【在 j*****d 的大作中提到】
: 我给你看看他给我的feedback，你就知道什么叫天竺威武了。
【在 j*****d 的大作中提到】
: 我给你看看他给我的feedback，你就知道什么叫天竺威武了。
p*r
14 楼
他给你了吗？
我作为路人赞助30，因为talking is cheap，show me your code
【在 l******r 的大作中提到】
: 50 伪币呢？
我作为路人赞助30，因为talking is cheap，show me your code
【在 l******r 的大作中提到】
: 50 伪币呢？
l*r
15 楼
他没给啊。所以跟他开个玩笑。我又不需要伪币。
就想看看他是不是守信用。
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
就想看看他是不是守信用。
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
j*d
16 楼
不好意思，以为这个帖子没有人追了。现在给你。
【在 l******r 的大作中提到】
: 50 伪币呢？
【在 l******r 的大作中提到】
: 50 伪币呢？
j*d
17 楼
写个java更好了，已经转了。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
j*d
18 楼
我给了。
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
【在 p**r 的大作中提到】
: 他给你了吗？
: 我作为路人赞助30，因为talking is cheap，show me your code
j*d
19 楼
请确认收到，信用事大。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
【在 l******r 的大作中提到】
: 他没给啊。所以跟他开个玩笑。我又不需要伪币。
: 就想看看他是不是守信用。
l*r
20 楼
给了。多谢收到。返还给pker他的30了。
找工作好烦啊。面试都拿不到。
【在 j*****d 的大作中提到】
: 请确认收到，信用事大。
找工作好烦啊。面试都拿不到。
【在 j*****d 的大作中提到】
: 请确认收到，信用事大。
j*d
21 楼
我是面试onsite拿到手软，可是，到处碰到这类3+黑，没有办法。请观看另外一帖，迷
思。
【在 l******r 的大作中提到】
: 给了。多谢收到。返还给pker他的30了。
: 找工作好烦啊。面试都拿不到。
思。
【在 l******r 的大作中提到】
: 给了。多谢收到。返还给pker他的30了。
: 找工作好烦啊。面试都拿不到。
相关阅读
怎样判断什么情况下不会出现race condition (转载)问一个capgap的傻问题问个OPT的问题[合集] H1-H4-H1身份问题G家一道题求bless，上班才第23天，受伤了请问有在中国建设银行纽约分行工作的吗？今天面了Amazon，真是面的奇烂无比明天Google Host Interview，求Bless递交H１转F2身份的申请后大概要多久批，2个月够吗？报offer，顺便问几个问题面试公司可以直接问现在的公司关于我的收入么问个google面试题OPT申请提交两周还没有收到Receipt（check也没有被cash），正常吗？这个offer接不接？刚电面完可以用opt提前工作吗？OPT status问题onsite 两个礼拜问结果跟recruiter电面时是问你什么答什么还是你自己可以扩展一些