3418.机器人可以获得的最大金币数
难度：中等
问题描述：
给你一个mxn的网格。一个机器人从网格的左上角(0,0)出发，目标是到达网格的右下角(m-1,n-1)。在任意时刻，机器人只能向右或向下移动。
网格中的每个单元格包含一个值coins[i][j]：
如果coins[i][j]>=0，机器人可以获得该单元格的金币。
如果coins[i][j]<0，机器人会遇到一个强盗，强盗会抢走该单元格数值的绝对值的金币。
机器人有一项特殊能力，可以在行程中最多感化2个单元格的强盗，从而防止这些单元格的金币被抢走。
注意：机器人的总金币数可以是负数。
返回机器人在路径上可以获得的最大金币数。
示例1：
输入：coins=[[0,1,-1],[1,-2,3],[2,-3,4]]
输出：8
解释：
一个获得最多金币的最优路径如下：
从(0,0)出发，初始金币为0（总金币=0）。
移动到(0,1)，获得1枚金币（总金币=0+1=1）。
移动到(1,1)，遇到强盗抢走2枚金币。机器人在此处使用一次感化能力，避免被抢（总金币=1）。
移动到(1,2)，获得3枚金币（总金币=1+3=4）。
移动到(2,2)，获得4枚金币（总金币=4+4=8）。
示例2：
输入：coins=[[10,10,10],[10,10,10]]
输出：40
解释：
一个获得最多金币的最优路径如下：
从(0,0)出发，初始金币为10（总金币=10）。
移动到(0,1)，获得10枚金币（总金币=10+10=20）。
移动到(0,2)，再获得10枚金币（总金币=20+10=30）。
移动到(1,2)，获得10枚金币（总金币=30+10=40）。
提示：
m==coins.length
n==coins[i].length
1<=m,n<=500
-1000<=coins[i][j]<=1000
问题分析：
这是一个中等难度的问题，但却很有意思。
当刚拿到这个题目，觉得每一步只有两种走法，要么向右，要么向下，那么只要比较一下哪一个方向获得的金币数量多，不就可以确定选哪个方向了吗？每一步都这样处理，获得的金币数量不就是最多的吗？但总觉得心里有些不踏实。在纸上用不同的网格测试，网格一这样处理确实可以，找到了“右下右下”的路径就是最佳路径，但网格二就不行了，按照先前的策略处理，应该是“右下下右”的路径，金币数为14，但按“下下右右”的路径，获得的金币数反而有15，可见那种每一步向获得金币数最多的方向走的策略是不行的，因而心里不踏实也是有道理的。如果再加上还要感化强盗，就更不好处理了。
那么如果找到从网格左上角到右下角的所有路径，并把每一条路径上的金币都找出来，再来处理其中感化强盗问题就简单多了。如果路径中的金币数量为负的个数只有一个或两个，直接感化掉就可以了，如果金币数量为负的个数多于两个，感化掉值最小的两个就可以了。
所以现在的问题就是如何求出从网格左上角到右下角的所有路径了。
对于mXn的网格，要从左上角到右下角，不管怎么走，向下要走m-1步，向右要走n-1步，而每一步只有向右和向下两种走法，这就是一个排列组合问题，通过递归可以实现。
程序如下：
#取出到达位置的金币
def get_coin(i,j,coins):return coins[i][j]#1表示向右，2表示向下,找出总共m+n-2步，每步只有1或2两种走法的全排列
def qlist(n):if n == 1:return ['1', '2']elif n == 2:return ['11', '12', '21', '22']else:a = chengfa(['1', '2'], qlist(n - 1))return adef chengfa(a, b):return [i + j for i in a for j in b]#对全排列进行处理，返回一个coins的走法全排列字符串，每个字符串通过1和2的组合给出了各种路径
def get_all_road(coins):m=len(coins)n=len(coins[0])b=m+n-2q=qlist(b)d=[x for x in q if x.count('1')==n-1]print('所有路径列表：',d)return d#根据flag指示的走法和当前坐标，给出下一个走到的位置坐标
def get_point(i,j,flag):if flag=='1':return [i,j+1]else:return [i+1,j]# 对一条线路lj处理，取得这条线路的金币数形成列表，并处理感化强盗问题，然后返回这条线路得到的最大金币数
def get_one_coin(coins, lj):print(f'解析{lj}线路')i=0 #左上角j=0 #左上角k=0 #记录感化次数m=[get_coin(0,0,coins)]for c in lj:if c=='1':print('向右',end=' ')else:print('向下',end=' ')d=get_point(i,j,c)i=d[0]j=d[1]e=get_coin(i,j,coins)m.append(e)print('按路径提取出的金币列表：',m)#统计小于0的个数n=len([x for x in m if x<0])if n>2:c=coin_more_2(m)else:c=coin_less_3(m)print('本线路获得的最大金币数：',c)return c#负数少于3个的时候处理办法
def coin_less_3(m):m=[x for x in m if x>=0]print('经过感化之后的金币列表：',m)return sum(m)
#负数多于2个的时候的处理办法
def coin_more_2(m):t1=min(m)m.remove(t1)t1=min(m)m.remove(t1)print('经过感化之后的金币列表：',m)return sum(m)#对所有路径进行处理，得到各条路径获得的最大金币，并取得其中的最大值返回
def get_all_coin(coins):road=get_all_road(coins)a=[]for i in road:a.append(get_one_coin(coins,i))return max(a)coins=eval(input('pls input coins='))
print('网格可以获得的最大金币数为：',get_all_coin(coins))运行实例一
pls input coins=[[0,1,-1,3],[1,-2,3,5],[2,6,-3,4]]
所有路径列表： ['11122', '11212', '11221', '12112', '12121', '12211', '21112', '21121', '21211', '22111']
解析11122线路
向右 向右 向右 向下 向下 按路径提取出的金币列表： [0, 1, -1, 3, 5, 4]
经过感化之后的金币列表： [0, 1, 3, 5, 4]
本线路获得的最大金币数： 13
解析11212线路
向右 向右 向下 向右 向下 按路径提取出的金币列表： [0, 1, -1, 3, 5, 4]
经过感化之后的金币列表： [0, 1, 3, 5, 4]
本线路获得的最大金币数： 13
解析11221线路
向右 向右 向下 向下 向右 按路径提取出的金币列表： [0, 1, -1, 3, -3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析12112线路
向右 向下 向右 向右 向下 按路径提取出的金币列表： [0, 1, -2, 3, 5, 4]
经过感化之后的金币列表： [0, 1, 3, 5, 4]
本线路获得的最大金币数： 13
解析12121线路
向右 向下 向右 向下 向右 按路径提取出的金币列表： [0, 1, -2, 3, -3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析12211线路
向右 向下 向下 向右 向右 按路径提取出的金币列表： [0, 1, -2, 6, -3, 4]
经过感化之后的金币列表： [0, 1, 6, 4]
本线路获得的最大金币数： 11
解析21112线路
向下 向右 向右 向右 向下 按路径提取出的金币列表： [0, 1, -2, 3, 5, 4]
经过感化之后的金币列表： [0, 1, 3, 5, 4]
本线路获得的最大金币数： 13
解析21121线路
向下 向右 向右 向下 向右 按路径提取出的金币列表： [0, 1, -2, 3, -3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析21211线路
向下 向右 向下 向右 向右 按路径提取出的金币列表： [0, 1, -2, 6, -3, 4]
经过感化之后的金币列表： [0, 1, 6, 4]
本线路获得的最大金币数： 11
解析22111线路
向下 向下 向右 向右 向右 按路径提取出的金币列表： [0, 1, 2, 6, -3, 4]
经过感化之后的金币列表： [0, 1, 2, 6, 4]
本线路获得的最大金币数： 13
网格可以获得的最大金币数为： 13
运行实例二
pls input coins=[[0,1,-1],[1,-2,3],[2,-3,4]]
所有路径列表： ['1122', '1212', '1221', '2112', '2121', '2211']
解析1122线路
向右 向右 向下 向下 按路径提取出的金币列表： [0, 1, -1, 3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析1212线路
向右 向下 向右 向下 按路径提取出的金币列表： [0, 1, -2, 3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析1221线路
向右 向下 向下 向右 按路径提取出的金币列表： [0, 1, -2, -3, 4]
经过感化之后的金币列表： [0, 1, 4]
本线路获得的最大金币数： 5
解析2112线路
向下 向右 向右 向下 按路径提取出的金币列表： [0, 1, -2, 3, 4]
经过感化之后的金币列表： [0, 1, 3, 4]
本线路获得的最大金币数： 8
解析2121线路
向下 向右 向下 向右 按路径提取出的金币列表： [0, 1, -2, -3, 4]
经过感化之后的金币列表： [0, 1, 4]
本线路获得的最大金币数： 5
解析2211线路
向下 向下 向右 向右 按路径提取出的金币列表： [0, 1, 2, -3, 4]
经过感化之后的金币列表： [0, 1, 2, 4]
本线路获得的最大金币数： 7
网格可以获得的最大金币数为： 8
运行实例三
pls input coins=[[1,3,1],[2,2,3],[4,5,3]]
所有路径列表： ['1122', '1212', '1221', '2112', '2121', '2211']
解析1122线路
向右 向右 向下 向下 按路径提取出的金币列表： [1, 3, 1, 3, 3]
经过感化之后的金币列表： [1, 3, 1, 3, 3]
本线路获得的最大金币数： 11
解析1212线路
向右 向下 向右 向下 按路径提取出的金币列表： [1, 3, 2, 3, 3]
经过感化之后的金币列表： [1, 3, 2, 3, 3]
本线路获得的最大金币数： 12
解析1221线路
向右 向下 向下 向右 按路径提取出的金币列表： [1, 3, 2, 5, 3]
经过感化之后的金币列表： [1, 3, 2, 5, 3]
本线路获得的最大金币数： 14
解析2112线路
向下 向右 向右 向下 按路径提取出的金币列表： [1, 2, 2, 3, 3]
经过感化之后的金币列表： [1, 2, 2, 3, 3]
本线路获得的最大金币数： 11
解析2121线路
向下 向右 向下 向右 按路径提取出的金币列表： [1, 2, 2, 5, 3]
经过感化之后的金币列表： [1, 2, 2, 5, 3]
本线路获得的最大金币数： 13
解析2211线路
向下 向下 向右 向右 按路径提取出的金币列表： [1, 2, 4, 5, 3]
经过感化之后的金币列表： [1, 2, 4, 5, 3]
本线路获得的最大金币数： 15
网格可以获得的最大金币数为： 15
通过计算得知，一个三阶矩阵有6条路径，四阶矩阵有20条路径，随着矩阵阶数的增加，路径数量呈几何级数增加，对于行列不等的矩阵也是如此，因此感叹只有借助于计算机地耐心解析，才可以更直观地观察到解决问题的过程，让结果更让人信服！
