动态规划--矩阵最大权值

这两段动态规划设计有什么不一样的吗？在运行某组数据时答案不一样
一、

#include 
#include 
using namespace std;

const int MAXN = 100 + 1;
int matrix[MAXN][MAXN];
int dp[MAXN][MAXN] = {0};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + matrix[i][j];
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}

二、

#include  
#include
using namespace std;

const int MAXN = 101;
int matrix[MAXN][MAXN] = {};
int dp[MAXN][MAXN] = {};
int main(){
    int n , m;
    scanf("%d%d", &n , &m);
    for(int i = 0; i <= n - 1; i++)
        for(int j = 0; j <= m - 1; j++)
            scanf("%d", &matrix[i][j]);
    for(int i = n - 1; i >= 0; i--)
        for(int j = m - 1; j >= 0; j--)
            dp[i][j] = max(dp[i + 1][j] , dp[i][j + 1]) + matrix[i][j];
    printf("%d", dp[0][0]);
}
  • 这个问题的回答你可以参考下: https://ask.csdn.net/questions/188217
  • 这篇博客你也可以参考下：知云登陆但不显示登陆二维码-问题解决
  • 除此之外, 这篇博客: 数据结构图的知识点大全总结（包括各类常见算法都有本人自己的独特分析）中的 二、图的存储结构 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  •         由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，即以一个数据域和多个指针域的结点表示图中的一个顶点，尽管可以实现图结构，但是以这种结构，如果各个结点的度数相差很大，按度数最大的顶点设置结点结构会造成很多存储单元的浪费，而若按每个顶点自己的度数设计不同的顶点结构，又带来操作的不便。如何实现物理存储是个难题。下面介绍前辈们提供的五种不同的存储结构。

    1 、邻接矩阵

           图的邻接矩阵存储方式使用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

    接下来分享几个实例来学习邻接矩阵

           从这个例子我们可以清楚的知道arc[i][j]=0说明顶点vi与vj之间没有边，若arc[i][j]=1说明顶点vi与vj之间有边。由于是无向图，所以无向图的邻接矩阵是对称矩阵即vi到vj有边，那么vj到vi也有边。

           如果我们要知道图中某个顶点的度那么只要将该顶点对应的行（或列）的元素值加起来，就是该顶点的度。

    下面在来看一个有向图的例子：

    如果arc[i][j]=0表示vi到vj不存在弧,arc[i][j]=1表示vi到vj存在弧。

    有向图讲究入度与出度，某个顶点的入度为该顶点对应的列上所有元素之和，某个顶点的出度为该顶点对应的行上的所有元素之和。该顶点入度加上出度就是该顶点的度。

    下面例看一个有向网图的例子：

    这里用∞表示一个不可能的极限值用来代表不存在。

    下面是图的邻接矩阵的结构定义：

    #include <iostream>
using namespace std;
typedef char VertexType;		//顶点类型
typedef int EdgeType;			//边权值类型

#define MAXVEX 100				//最大顶点数
#define INFINITY 65535			//用65535代表∞
typedef struct _MGraph			//图的邻接矩阵存储方式定义
{
	VertexType vexs[MAXVEX];	//定义顶点数组
	EdgeType arc[MAXVEX][MAXVEX];	//定义邻接矩阵
	int NumVexs;				//图中顶点数
	int NumEdges;				//图中边数
}MGraph;

    2、邻接表

    邻接表示不错的一种图的存储结构，但是我们发现对于边数相对顶点较少的图，这种结构时存在对存储空间的极大浪费。如我们要处理像下图这样的稀疏有向图：
     

    除了一条弧有权值外，没有其他弧，那么这就造成了存储空间的极大浪费。

    这里我们采取了邻接表的存储方式。邻接表就是把数组与链表相结合的存储方法。

    邻接表处理步骤如下：

    1.图中顶点用一维数组存储，另外每个数据元素还需存储指向第一个邻接点的指针，以便于查找该顶点的信息。

    2.图中每个顶点的vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储。无向图称为顶点vi的边表，有向图则称为vi作为弧尾的出边表。

    下面举个无向图的邻接表的例子：

    由这个例子知道顶点表的各个结点由data域和firstedge域（指针域）两个域表示。data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域用来存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

    若是有向图，邻接表结构同样类似，不过有向图有方向，所以有向图有邻接表与逆邻接表两种方式，看如下例子：

    当然我们可以建立一个有向图的逆邻接表，即对每个顶点都建立一个以顶点vi都建立一个以vi为弧头的表，上例的逆邻接表如下：

    此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。

    对于带权值的网图，可以在边表结点中再定义一个weight的数据域，存储权值信息即可。

    下面给出图的邻接表结构的定义：

    typedef char VertexType;		//顶点类型
typedef int EdgeType;			//边权值类型
#define MAXVEX 100				//最大顶点数
typedef struct _EdgeNode		//边结点
{
	int adjvex;					//邻接点域，存储该顶点对应下标
	EdgeType weight;			//用于存储权值，非网图可以不需要
	struct _EdgeNode *next;		//链域，指向下一个邻接点
}EdgeNode;

typedef struct _VexNode			//顶点结点
{
	VertexType data;			//数据域，存储结点信息
	struct _VexNode *firstedge;	//指针域，存储指向第一个邻接点的指针（边表头指针）
}VexNode,AdjList[MAXVEX];

typedef struct
{
	AdjList adjlist;
	int numvexs;				//图中顶点数
	int numedge;				//图中边数
}GraphAdjList;

    3、十字链表

    对于有向图来说，邻接表是有缺陷的，只知道出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。为了解决这个问题，我们要引出有向图的一种存储方法：十字链表。

    实质上，十字链表就是将邻接表与逆邻接表结合起来。

    我们需要重新定义顶点表结构如下图：

    其中firstin表示入边表头指针，指向该顶点的入边表中的第一个顶点（相当于逆邻接表），firstout表示出边表头指针，指向该顶点的出边表中的第一个结点（相当于邻接表）。

    重新定义边表结构如下：

    其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的·下一条边，taillink是指向起点相同的下一条边。如果是网，还可以在增加一个weight域来存储权值。

    下面来看一个例子：

    上图中的虚线箭头其实就是该图的逆邻接表（入边（顶点做弧头））。实线就是该图的邻接表（出边（顶点做弧尾））。

    有向图的十字链表存储方式代码如下：

    typedef char VertexType;		//顶点类型
typedef int EdgeType;			//边权值类型
#define MAXVEX 100				//最大顶点数
typedef struct _EdgeNode
{
	int tailvex;				//弧起点（弧尾）在顶点表的下标
	int headvex;				//弧终点（弧头）在顶点表的下标
	struct _EdgeNode *headlink;	//入边表指针域，用来指向终点相同的下一条边
	struct _EdgeNode *taillink;	//出边表指针域，用来指向起点相同的下一条边
}EdgeNode;

typedef struct _VexNode
{
	VertexType data;			//用来存放顶点信息
	EdgeNode *firstin;			//指针域，用来指向入边表的第一个顶点（即该顶点做弧头）
	EdgeNode *firstout;			//指针域，用来指向出边表的第一个顶点（即该顶点做弧尾）
}VexNode,Adjvexs[MAXVEX];

typedef struct
{
	Adjvexs adjvexs;			//定义顶点数组
	int numvexs;				//该图的顶点数
	int numedges;				//该图的边数
}GraphCrossLinkList;

    4、邻接多重表

    十字链表是对有向图的优化存储结构，对于无向图，如果我们关注的是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已经访问的边做标记，删除某一条边等操作。那就意味，需要找到这条边的两个边表结点进行操作，显然这是比较麻烦的。

    所以我们重新定义边表结点结构如下：
     

    其中ivex与jvex是与某条边依附的两个顶点在顶点表中下标。ilink是指依附顶点ivex的下一条边，jlink是指依附顶点jvex的下一条边。这就是邻接多重表结构。

    看下面的例子：

    此例中图中有4个顶点，五条边。然后依次按照顺序连线，当我们需要删除（v0，v2）这条边时，只需要将图中6和9的指针域置为空。

    我想大家应该明白，邻接多重表与邻接表的区别，仅仅是在于同一条边在邻接多重表中用一个结点表示，而在邻接表中用两个边表结点表示。

    5、边集数组

    边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。如下图是一个边集数组：

    显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高，因此它更适合对边依次进行处理的操作。而不适合对顶点相关的操作。

  • 您还可以看一下 韦语洋（Lccee）老师的一机一码加密、被破解自动销毁随时授权回收升级系列视频课程课程中的 演示如何破解一个软件绕过注册机(仅作为后续课程的了解)小节, 巩固相关知识点
第一段代码中，二维数组 matrix 和 dp 的下标从 1 开始，而第二段代码中下标从 0 开始。这导致了在读入数据和计算 dp 值时需要进行一定的调整。

第二段代码中，计算 dp 值时使用了另一种顺序，即从终点 (n-1, m-1) 开始往起点 (0, 0) 倒推。这样可以避免在 dp 过程中对 dp 数组执行赋值操作，从而可以使代码更加简洁。

在第二段代码中，二维数组 matrix 和 dp 的大小均取为 MAXN，而在第一段代码中，二维数组的大小分别为 MAXN * MAXN 和 MAXN * MAXN。这样会造成空间浪费。