跳转至

收集硬币

1、题目描述

给定一个m行,n列的正整数矩阵,每个矩阵元素的数字代表有多少硬币 有两个机器人进行收集硬币的操作,第一个机器人的起始点为[0,0],结束点为[m-1,0] 第二个机器人的起始点为[0,n-1],结束点为[m-1,n-1] 机器人收集硬币的下一步有三种操作(设当前坐标为x,y): - 左下角 [x+1,y-1] - 下方 [x+1,y] - 右下角 [x+1,y+1]

找出两个机器人共同收集最多硬币的数量

注意: - 如果n<2,返回-1 - 同一个位置的硬币只能收集一次

输入:

第一行为两个数字,行与列, m,n

第二行为 m*n 个数字

输出:

两个机器人共同收集最多硬币的数量

限制条件:

  • 0<= m <= 110
  • 0<= n <= 110
  • 0<= grid[i][j] <= 12100

实例1:

输入:

6 5
9 10 15 12 11 7 5 11 6 8 4 1 27 13 17 2 4 18 2 1 15 3 22 6 10 8 2 5 9 6

输出:

130

解释:

image-20191124182009939

实例2:

输入:

5 4
3 6 8 2 5 2 4 3 1 1 20 10 1 1 20 10 1 1 20 10

输出:

73

2、解题思路

如上面题目所示,并不能仅考虑一个机器人所得到最大的值,需要同时考虑两个机器人,但是我们发现,机器人只能从上到下的方向前进,并且每一行都有两个位置分别给到机器人1机器人2

由于机器人每走一步,都可能产生三种可能性,并且需要考虑两个机器人不会占用同一个节点的情况,采用自底向上进行更新的动态规划

首先,目标值为机器人1走到左下角的位置,机器人2走到右下角的位置,这时候,从这个点作为起点

初始化:

dp[(x,y)] 表示机器人1从x点走到左下角 加上机器人2走到右下角所得到的最多的硬币数

状态转换方程:

采用倒退的方式,我们找出能够得到dp[(x,y)]的所有组合,然后利用dp[(x,y)]的值进行更新当前组合的值

如何得到能够得到当前点的所有组合呢?

只需要找出所有能够到达x点的上一层的点,以及所有能够到达y的上一层的点,这些点记性组合即可(两个点不能相同)

def get_upper(pos):
    m, n = pos // col, pos % col
    temp = []
    for i in [-1, 0, 1]:
        if available(m - 1, n + i):
            temp.append((m - 1) * col + n + i)
    return temp

上面的函数就找出的能够得到当前pos的所有的上层节点

如果[m,n]=>[x,y]
dp[(m,n)] = max(dp[(m,n)],dp[(x,y)]+ grid[m] + grid[y] )

坐标和序号可以相互转换

代码实现:

from collections import defaultdict
from collections import deque
from itertools import product

row, col = map(int, input().strip().split())


# 坐标验证
def available(m, n):
    return 0 <= m < row and 0 <= n < col


def get_upper(pos):
    m, n = pos // col, pos % col
    temp = []
    for i in [-1, 0, 1]:
        if available(m - 1, n + i):
            temp.append((m - 1) * col + n + i)
    return temp


mapping_index = {index: val for index, val in enumerate(map(int, input().strip().split()))}
mem = defaultdict(int)
last_left = (row - 1) * col
last_right = row * col - 1
mem[(last_left, last_right)] = mapping_index[last_left] + mapping_index[last_right]

ans = -1

if col < 2:
    ans = -1
elif col == 2:
    ans = sum(map(int, input().strip().split()))
else:
    d = deque()
    d.append([last_left, last_right])
    while d:
        l, r = d.popleft()
        left = get_upper(l)
        right = get_upper(r)
        for x, y in product(left, right):
            if x != y:
                mem[(x, y)] = max(mem[(x, y)], mem[(l, r)] + mapping_index[x] + mapping_index[y])
                d.append([x, y])
        ans = mem[(0, col - 1)]
print(ans)

#
# 6 5
# 9 10 15 12 11 7 5 11 6 8 4 1 27 13 17 2 4 18 2 1 15 3 22 6 10 8 2 5 9 6
# => 130
#

#
# 5 4
# 3 6 8 2 5 2 4 3 1 1 20 10 1 1 20 10 1 1 20 10
# => 73
#