197、【动态规划】AcWing —— 901. 滑雪(C++版本)
题目描述
原题链接:901. 滑雪
解题思路
整体思路就是依次进行递归遍历,从不同的起始位置出发找到一条最长区域路径。每次探寻时,从上下左右四个方向寻找,最终找到一条最长路径。
- 动态规划五步曲:
(1)dp[i][j]含义: 位于(i, j)时,具有的最长区域路径长度。
(2)递推公式: d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d f s ( i + d x , j + d y ) + 1 ) dp[i][j] = max(dp[i][j], dfs(i + dx, j + dy) + 1) dp[i][j]=max(dp[i][j],dfs(i+dx,j+dy)+1),意为在已有的结果中和向上下左右某一个方向继续探索后,找到一个最大区域长度结果。
(3)dp数组初始化: dp[i][j] = 1,每个自身代表一个长度。
(4)遍历顺序; 树的后序遍历。
(5)举例: (省略)
直接对dp数组赋值初始化
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 上下左右四个方向探索
int dp[N][N], g[N][N];
int n, m;
int dfs(int x, int y) {
if(dp[x][y] != 1) return dp[x][y]; // 当前位置最优情况已被探索过,则直接返回
for(int i = 0; i < 4; i++) { // 探寻上下左右四个方向中的最大区域长度
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]) {
dp[x][y] = max(dp[x][y], dfs(a, b) + 1);
}
}
return dp[x][y];
}
int main() {
// 1、输入数据并初始化pd数组
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &g[i][j]);
dp[i][j] = 1;
}
}
// 2、枚举从不同起始位置开始,得到的最大区域长度结果
int res = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
res = max(res, dfs(i, j));
}
}
// 3、输出结果
printf("%d\n", res);
return 0;
}
对dp数组全部初始化后,再进行合法赋值
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 上下左右四个方向探索
int dp[N][N], g[N][N];
int n, m;
int dfs(int x, int y) {
if(dp[x][y] != -1) return dp[x][y]; // 当前位置最优情况已被探索过,则直接返回
dp[x][y] = 1;
for(int i = 0; i < 4; i++) { // 探寻上下左右四个方向中的最大区域长度
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]) {
dp[x][y] = max(dp[x][y], dfs(a, b) + 1);
}
}
return dp[x][y];
}
int main() {
// 1、输入数据并初始化pd数组
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &g[i][j]);
}
}
memset(dp, -1, sizeof dp);
// 2、枚举从不同起始位置开始,得到的最大区域长度结果
int res = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
res = max(res, dfs(i, j));
}
}
// 3、输出结果
printf("%d\n", res);
return 0;
}
相关文章
- 托管C++线程锁实现 c++11线程池
- C++应该被看成是个语言集合——四种语言(C语言,OO语言,泛型语言,STL)
- 191、【动态规划】AcWing —— 900. 整数划分:完全背包解法+加减1解法(C++版本)
- 183、【动态规划】leetcode ——516. 最长回文子序列(C++版本)
- 181、【动态规划】leetcode ——72. 编辑距离(C++版本)
- 180、【动态规划】leetcode ——583. 两个字符串的删除操作:两种动态规划思路(C++版本)
- 179、【动态规划】leetcode ——115. 不同的子序列(C++版本)
- 164、【动态规划】leetcode ——213. 打家劫舍 II:环形列表线性化(C++版本)
- 160、【动态规划】leetcode ——279. 完全平方数:二维数组+一维滚动数组(C++版本)
- 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本)
- 157、【动态规划】leetcode ——377. 组合总和 Ⅳ:二维数组+一维滚动数组(C++版本)
- 158、【动态规划】leetcode ——518. 零钱兑换 II:二维数组+一维滚动数组(C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- 148、【动态规划】leetcode ——63. 不同路径 II:递归法+迭代法(C++版本)
- 146、【动态规划】leetcode ——746. 使用最小花费爬楼梯:递归法+迭代法(C++版本)
- 145、【动态规划】leetcode ——70. 爬楼梯:暴力法+动态规划(C++版本)