这一题如何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了。
: 找工作好烦啊。面试都拿不到。
相关阅读
Brief on Buy American, Hire American EO中国企业在美国的分部 那个能去？bloomberg在sf的hiring event电面冷冻期多久?［请教］H1b Grace Period需要140 Approve么H1B抽签要作废了？求助一道sql问题,谢谢面试面了一半，被现公司Layoff，我该怎么说？问个美国人简历的问题学历低的老板很多，高学历的人多数都在做打工仔从湾区搬LA的话，是不是硬件必须得转软件了？Quora 已经18亿了谁取的名字relocate 到一个小地方贡献一道面试题关于果家ICT我艹，Uber的经历在简历上变成负资产了！那个自杀的UBER员工才17万， 为什么版上吹嘘说都有50万？同学们，学习一下阿三如何包装申请intern亚麻最近招人力度大了？