蓝桥杯算法训练-拿金币

时间：2025-02-09 17:36:41

蓝桥杯练习新题，dp类，比较简单。

问题描述

有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式

第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式

最多能拿金币数量。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

数据规模和约定

n<=1000

解题思路：

        我觉得没啥好说的，典型的dp问题，规定了只能向下或右移动，因此dp数组每个位置即为上方和左方格子中较大的一项加当前位置的数，然后考虑棋盘上边缘和左边缘的特殊情况即可。

        数组索引的操作可以自己画个图推一下即可。

n = int(input())
square = []
for i in range(n):
    (list(map(int, input().split())))
def dp_matrix(square):
    # 处理传入的矩阵，使其变成动态规划的数组
    for a in range(1, (n - 1) * 2 + 1):
        if a < n:
            start = 0
            end = a + 1
        else:
            start = a - (n - 1)
            end = n
        for i in range(start, end):
            j = a - i
            if i == 0:  # 判断此处位置是否在棋盘上边缘，如果是则只能从左侧格子移到此位置
                square[i][j] = square[i][j] + square[i][j-1]
            elif j == 0:    # 判断此处位置是否在棋盘左边缘，如果是则只能从上方格子移到此位置
                square[i][j] = square[i-1][j] + square[i][j]
            else:   # 如果不在期盼边缘，则可以从上方或左侧格子移到此位置，求出移到此位置的最大金币数
                square[i][j] = square[i][j] + max(square[i-1][j], square[i][j-1])
    return square[-1][-1]
print(dp_matrix(square))

欢迎大家讨论，如果有更优的解可以在下面留言！

相关文章