看到一题 求思路

glambertjay 发表于 2020-8-28 11:38
那我帖子里提到的这个sample能跑出来吗？我觉得正向就必须考虑路径的选择。

test过没问题的，我私聊你啦，咱们可以share下不同方法的代码

记忆化递归，算得210，其他的没测过。

1. def bt(i,j,d,p):
   
2.         if i == m-1 and j == n-1:
   
3.                 return max(1-int(array[i][j]),1)
   
4.         if i >= m or j >= n:
   
5.                 return float('inf')
   
6.         if (i,j,d,p) in memo:
   
7.                 return memo[(i,j,d,p)]
   
8.         if array[i][j] != 'D' and array[i][j] != 'P':
   
9.                 val = int(array[i][j])
   
10.                 if d and val > 0:
    
11.                         val = int(array[i][j])*2
    
12.                         d = False
    
13.                 elif p and val < 0:
    
14.                         val = 0
    
15.                         p = False
    
16.         else:
    
17.                 val = 0
    
18.         v1 = bt(i+1,j,d or array[i][j] == 'D',p or array[i][j] == 'P')
    
19.         v2 = bt(i,j+1,d or array[i][j] == 'D',p or array[i][j] == 'P')
    
20.         memo[(i,j,d,p)] = max(min(v1,v2)-val,1)
    
21.         return memo[(i,j,d,p)]
    
22. array = [['-1']*5,['D','1','2','3','4'],['-1','-2','-3','1','2'],['5','10','-1','1','2'],['10','5','50','-1','-300']]
    
23. m,n = len(array),len(array[0])
    
24. memo = {}
    
25. res = bt(0,0,False,False)
    
26. print(res)

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i]

我觉得这俩本质上的思考方式不一样吧。
记忆递归的思路就像你代码写的，正想qiongju，不需要去考虑D或是P后面要选哪个，因为都会走到右边或是下边，直接比当前走到这个格子的值就好了
reverse DP是从结果出发，从最后结果出发到当前格子的最优解是什么。
这两个的区别可以类比为一个是bottom up的过程一个是top down的过程。

State挺多的。

用BinarySearch吧！