狗onsite

wenyitiger 发表于 2018-5-24 15:18
第三题感觉是一道DP 状态跟上一行从左进 从右进 有关

第三题，感觉像个minimun spanning tree？

wenyitiger 发表于 2018-5-24 15:18
第三题感觉是一道DP 状态跟上一行从左进 从右进 有关

哦，没看到要求是逐行的，觉得DFS更好一些。

yyyxxxccc 发表于 2018-4-25 09:51
是的必须逐行修，并且你没有办法从一行的中间直接进入下一行。必须从一行的最左边或者最右边进入下一行

如果必须是最左或左右，如果每行都有坏的，那岂不是就是左一行右一行就可以了？

不是啊 比如如果一行很长 并且坏的集中在最左边，那minimum cost可能就是把左边修完再折返

1. def minstep(matrix):
   
2.     N = len(matrix[0])
   
3.     M = len(matrix)
   
4.     data = [[0,0] for x in xrange(M)]
   
5.     for index in xrange(M):
   
6.         #right
   
7.         data[index][1] = (N - matrix[index].index(1))*2 -1
   
8.         #left
   
9.         data[index][0] = (N - matrix[index][::-1].index(1))*2 - 1
   
10.         
    
11.     cache = {}
    
12.     def dfs(leftright,level):
    
13.         if level == 0:
    
14.             if leftright == 0:
    
15.                 return N
    
16.             else:
    
17.                 return data[level][1]
    
18.         if (leftright,level) not in cache:
    
19.             cache[(leftright,level)] = min(dfs(leftright,level-1) + data[level][leftright], dfs(1-leftright,level-1) + N)
    
20.         
    
21.         return cache[(leftright,level)]
    
22.    
    
23.     return min(dfs(0,M-1),dfs(1,M-1))
    
24. 
    

复制代码

写了下第三题 欢迎大家讨论 :)  思路就是dfs(leftright,level) 表示第level行进 从左或者从右出 然后memorization一下