动态规划——礼物的最大价值问题用python写出来及输入
时间: 2023-08-01 15:05:58 浏览: 56
礼物的最大价值问题是一个经典的动态规划问题。假设有一个m行n列的矩阵,每个格子里放着一个礼物,每个礼物的价值不同。你可以从矩阵的左上角出发,每次只能向下或者向右移动一格,直到到达矩阵的右下角。请计算出你最多能拿到多少价值的礼物。下面是使用Python实现的代码:
```python
def max_value(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
for j in range(1, cols + 1):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + matrix[i - 1][j - 1]
return dp[rows][cols]
# 测试
matrix = [[1, 10, 3, 8],
[12, 2, 9, 6],
[5, 7, 4, 11],
[3, 7, 16, 5]]
print(max_value(matrix))
```
输入的格式是一个二维列表,每个元素代表矩阵中对应位置的礼物价值。例如,上面的测试输入对应的矩阵为:
```
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
```
你可以根据需要修改输入格式,比如将每行数字用空格隔开,或者使用逗号分隔等。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)