python - 寻找价值最高的路线
问题描述
给定下面的数据,找到从左下角到右上角的最高价值路线。
[{ 0, 0, 0, 6 },
{ 2, 0, 0, 2 },
{ 0, 1, 1, 1 },
{ 3, 0, 0, 0 }]
go can only move right (east) or up (north)
Highest value route here is 3 -> 0 -> 1 -> 1 -> 1 -> 2 ->6 = 14
我应该如何处理这个问题。我下面作为伪代码的方法是否正确?
max = 0
array = defined_array
i = len(array)
k = 0
def path(i,j):
total = 0
for j in range(4):
k = j;
total = total + int(array[i][j])
if total > max:
max = total
return path(--i,k)
key= 3
def path(i,j):
for i in range(i):
for j in range(array[i]):
total = total + array[i][j]
解决方案
我根本没有得到你的方法。
这就是简单动态规划问题。
将其视为二维数组Arr[4][4]
[{ 0, 0, 0, 6 },
{ 2, 0, 0, 2 },
{ 0, 1, 1, 1 },
{ 3, 0, 0, 0 }]
制作另一个 4*4 的 dp 数组
您需要做的第一件事是初始化基本案例。
所以第一列和最后一行是我们的基本情况。
dp[0][3]=Arr[0][3];
在此之后为第一列
dp[i][0]=dp[i+1][0]+Arr[i][0];
最后一行
dp[3][i]=dp[3][i-1]+Arr[3][i];
对于其他值
dp[i][j]=max(dp[i][j-1],dp[i+1][j])+Arr[i][j];
,我们将选择最大值。
我们的 dp 数组看起来像这样,答案是 14
[{ 5, 5, 5, 14 },
{ 5, 5, 5, 8 },
{ 3, 4, 5, 6 },
{ 3, 3, 3, 3 }]
推荐阅读
- mysql - 如何验证mybatis配置文件中的poolpingquery配置是否正确执行?
- google-maps - 如何在谷歌地图上找到最近的医院
- node.js - Docker 容器在主机上生成 docker 容器
- ios - 如何在objective-c中访问swift 5结果枚举类型
- python - 在 python 中将 asyncio 与 fork 混合:坏主意?
- c# - 将 C# 代码与 roslyn 合并:注释消失
- intellij-idea - PyCharm 右击开始以当前路径作为参数运行
- angular - 使用 Angular 10 应用程序中的 ngx-microsoft-bot-framework 会出现错误 No provider for ComService
- android - RecyclerView 不显示来自 firebase 数据库的信息
- html - 当我使用角度输入注册表时,我想根据年龄打印如果人是未成年人或主要或老年人