更难的矩阵取数问题(dp)

2024-02-19 09:38
文章标签 问题 dp 矩阵 取数 更难

本文主要是介绍更难的矩阵取数问题(dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

更难的矩阵取数问题

分析: 只走一次的问题我们之前分析过。现在要走两次,有什么好办法呢? 我们设想,有两个人都从左上角走到右下角,这和走到终点再返回是一样的,我们可以dp么?怎么dp?先看看按照之前那种方法dp两次行不行? 看下图:

如果第一条路径先找最优的,就要走路径(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)。

但是这样(1,5)和(5,3)的两个100就分开了,第二条路径至多取到一个100。事实上,我们可以选取这样的两条路径:

(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)

这两条路径取得了全部的100,这两条路径是最优的!



没招了么?其实我们可以“两个人一起”dp(让两个人同时走)。

用dp[x1][y1][x2][y2]表示第一个人在(x1,y1) 并且第二个人在(x2,y2)时的最大值。

我们有初值dp[1][1][1][1] = a[1][1], 求的是dp[m][n][m][n]。

问题来了: 每个人走一步,状态转移是什么?

dp[x1][y1][x2][y2] = max{dp[x1’][y1’][x2’][y2’]} + a[x1][y1] + a[x2][y2]
其中(x1’,y1’)是(x1,y1)的邻居,(x2’,y2’)是(x2,y2)的邻居。

事实上,因为我们有这个等式提示我们其实只要用3维就可以表示这个矩阵,因为 y2 = x1 + y1 – x2所以那一维可以用走多少步表示出来。

dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1] + a[x2][y2]

图中为step做了编号。

然而这个dp并没有体现出走到相同格子,数字仅计算一次的要求。那么我们加上这个条件:如果x1 = x2,dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1]。


最后,我们来提供输入输出数据,由你来写一段程序,实现这个算法,只有写出了正确的程序,才能继续后面的课程。


输入

第1行:2个数M N,中间用空格分隔,为矩阵的大小。(2 <= M, N <= 200)
第2 - N + 1行:每行M个数,中间用空格隔开,对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

输出

输出能够获得的最大价值。

输入示例

3 3
1 3 3
2 1 3
2 2 1

输出示例

17


代码:

#include<iostream>
#include<cstring>
using namespace std;int dp[405][205][205];  //放在main()里会崩,因为数组太大
int a[205][205];  //放里面一个超大的数据过不了int main()
{int m,n;cin>>m>>n;for(int i=0;i<n;i++){for(int j=0;j<m;j++)cin>>a[i][j];}memset(dp,0,sizeof(dp));dp[0][0][0]=a[0][0];int x1,y1,x2,y2;for(int i=1;i<n+m;i++){for(x1=0;x1<n&&i-x1>=0;x1++){for(x2=0;x2<n&&i-x2>=0;x2++){if(x1>=1&&x2>=1)  //不在起点dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2>=1)  //x1不动,x2动。  即x1代表向右走,x2向下走dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1>=1&&x2<=i-1)  //x1动,x2不动。dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2<=i-1)  //x1、x2都不动dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));}}}cout<<dp[n+m-1][n-1][n-1]<<endl;return 0;
}

这篇关于更难的矩阵取数问题(dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724278

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符