现在是2025-4-15 12：24，ok，做完这题去吃饭。

在做这题之前我们有必要讲讲关于容器vector的相关知识

1. 基本概念

vector 是 C++ 标准模板库（STL）中的一个序列容器，它封装了动态大小数组的功能。与普通数组相比，vector 具有自动管理内存、动态扩展大小的优势。

主要特点：

• ​动态数组：可以动态调整大小
• ​连续存储：元素在内存中是连续存储的
• ​随机访问：支持通过下标快速访问元素
• ​自动内存管理：自动处理内存分配和释放

2. 基本用法

2.1 头文件

#include <vector>

2.2 声明和初始化

// 空vector
vector<int> v1;

// 指定初始大小
vector<int> v2(10); // 10个元素，默认值为0

// 指定初始大小和初始值
vector<int> v3(10, 5); // 10个元素，每个都是5

// 使用初始化列表
vector<int> v4 = {1, 2, 3, 4, 5};

// 从数组初始化
int arr[] = {1, 2, 3};
vector<int> v5(arr, arr + sizeof(arr)/sizeof(int));

// 拷贝构造
vector<int> v6(v4);

2.3 二维vector

// 声明3行4列的二维vector，初始值为0
vector<vector<int>> matrix(3, vector<int>(4));

// 初始化二维vector
vector<vector<int>> matrix2 = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

3. 常用操作

3.1 访问元素

vector<int> v = {1, 2, 3, 4, 5};

// 使用下标访问（不检查边界）
cout << v[2]; // 3

// 使用at()访问（会检查边界，越界抛出异常）
cout << v.at(2); // 3

// 访问第一个和最后一个元素
cout << v.front(); // 1
cout << v.back();  // 5

3.2 添加元素

vector<int> v;

// 在末尾添加元素
v.push_back(1);
v.push_back(2);
v.push_back(3);

// 在指定位置插入元素
v.insert(v.begin() + 1, 10); // 在第二个位置插入10

3.3 删除元素

vector<int> v = {1, 2, 3, 4, 5};

// 删除末尾元素
v.pop_back();

// 删除指定位置元素
v.erase(v.begin() + 1); // 删除第二个元素

// 删除指定范围内的元素
v.erase(v.begin(), v.begin() + 2); // 删除前两个元素

// 清空vector
v.clear();

3.4 大小和容量

vector<int> v = {1, 2, 3};

cout << v.size();     // 当前元素个数：3
cout << v.capacity();  // 当前分配的存储空间大小
cout << v.empty();    // 是否为空：0（false）

// 调整大小
v.resize(5);          // 大小变为5，新增元素默认初始化为0
v.resize(8, 100);     // 大小变为8，新增元素初始化为100

// 预留空间（避免频繁重新分配内存）
v.reserve(100);       // 预留100个元素的空间

4. 迭代器

vector<int> v = {1, 2, 3, 4, 5};

// 使用迭代器遍历
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

// 使用反向迭代器
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";
}

// 基于范围的for循环（C++11）
for (int num : v) {
    cout << num << " ";
}

5. 算法操作

#include <algorithm>

vector<int> v = {5, 3, 1, 4, 2};

// 排序
sort(v.begin(), v.end()); // 升序
sort(v.begin(), v.end(), greater<int>()); // 降序

// 查找
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Found at position: " << it - v.begin();
}

// 反转
reverse(v.begin(), v.end());

// 去重（需要先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

ok，通过上面的知识，至少我们知道了怎么创建一个一维的容器/二维的容器/如何访问其中的元素/排序等，其余我们暂时用不到，掌握上面这些就足够了。

ok~，我们进入正题，我想通过这题帮助大家入门一下动态规划。

1. 理解问题并识别动态规划适用性

常见适用场景：

• 最值问题（最大值/最小值）
• 计数问题（多少种方式/路径）
• 存在性问题（是否可行/可达）

2. 定义状态

状态定义是动态规划最关键的一步，需要明确：

• dp[i] 或 dp[i][j] 等状态表示什么含义
• 状态参数的选择（通常与问题变量相关）

示例：

• 斐波那契数列：dp[i] 表示第i个斐波那契数
• 背包问题：dp[i][j] 表示前i个物品在容量j时的最大价值
• 路径问题：dp[i][j] 表示到达(i,j)位置的最大/最小路径和

3. 建立状态转移方程

核心思想：当前状态如何从已知状态推导而来

常见形式：

dp[i] = dp[i-1] + dp[i-2]          // 斐波那契数列
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]  // 路径问题

4. 确定初始条件和边界情况

必须明确：

• 最小子问题的解（递归基）
• 数组的初始值
• 边界情况的处理方式

示例：

// 斐波那契数列
dp[0] = 0;
dp[1] = 1;

// 路径问题
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

5. 确定计算顺序

选择原则：

• 确保计算当前状态时，所依赖的子问题都已被计算
• 常见顺序：
  • 自底向上：从最小子问题开始，逐步求解更大问题
  • 自顶向下：记忆化搜索（递归+缓存）

示例：

// 自底向上计算斐波那契数列
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

可能通过上面的动态规划步骤你还不是特别理解，怎么一步步实施还是不太清楚。那我们开始看今天的题目。

题目

题目描述

Ipomy 现在来到了阿兹特克宝藏堆中。这些宝藏散落放在一个 m * n 的网格上，每个宝藏都有一个价值。Ipomy 自然是希望将所有宝藏统统拿走，但他在走出迷宫时，不小心中了魔咒，一次只能向下或向右移动一步。假设 Ipomy 身处网格的左上角，而古城的出口在右下角，他想在离开古城前，拿到价值之和尽可能大的宝藏。请你编写程序，帮助他计算他可以拿到的最大价值之和。

样例解释

一路向下走，取到 4 和 8，接着一路向右走，取到 9, 10 和 11，价值之和为 42。

输入描述

多组输入。

每组输入的第一行为两个整数 m 和 n，用来描述网格的规格。保证 1 <= m, n <= 1000。

接下来的 m 行，每行 n 个整数，表示每个格子上面的宝藏的价值。输入数据保证 Ipomy 起始所在处没有宝藏，即价值为 0，以及每个宝藏的价值均在 int 型的表示范围内。

输出描述

多组输出。

每组输出占据一行，为一个整数，表示最大的价值之和。

样例输入

3 4 
0 5 2 3
4 5 6 7 
8 9 10 11 

样例输出

42

# include<vector>
# include<algorithm>
# include<iostream>
using namespace std;

int maxTreasureValue(vector<vector<int>>& grid)
{
	int m = grid.size();  // 网格的行数
	int n = grid[0].size();  // 网格的列数
	 
	// 创建DP数组
	vector<vector<int>> dp(m,vector<int>(n,0));
	
	// 初始化起点
	dp[0][0] = 0;
	
	// 初始化第一行
	for(int j=1;j<n;++j)
	{
		dp[0][j] = dp[0][j-1]+grid[0][j];
	}
	
	// 初始化第一列
	for(int i=1;i<m;i++)
	{
		for(int j=1;j<n;++j)
		{
			// 取上方或左方的最大值，然后加上右下角的值
			dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j];
		}
	}
	
	return dp[m-1][n-1]; // 返回右下角的最大价值
}

int main()
{
	int m,n;
	while(cin>>m>>n) // 多组输入
	{
		vector<vector<int>> grid(m,vector<int>(n));
		for(int i=0;i<m;++i)
		{
			for(int j=0;j<n;j++)
			{
				cin>>grid[i][j];
			}
		}
		
		cout<<maxTreasureValue(grid)<<endl;
	}
	
	return 0;
	
}

如果你仔细看过这个题目，然后看了这个代码，那么你大概会看到这样一个结构：

创建一个动态数组-> 依据现有的值初始化动态数组->在规定界内，判断前一刻的最优值（这个最优值是之前的之前计算出来的，额，好像有点抽象），找到前一刻的最优值后，在加上当前的值，组成当前最优值，这个最优值将被用作下一刻的 用于判断找  下一刻的前一刻的最优值，然后就是循环

其实动态规划真的难吗？其实没有那么难，或许动态规划那个数组的意义你可能还没有完全理解，但是时间会让你理解一切~，如果你都看到这里了，我相信你以后会熟练使用这个动态规划。

好啦，今天就分享一篇，明天期中考试，好好准备，祝我赢！

吃饭咯~