本文主要是介绍树状数组优化dp，2617. 网格图中最少访问的格子数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
给你一个下标从 0 开始的
m x n整数矩阵grid。你一开始的位置在 左上角 格子(0, 0)。当你在格子
(i, j)的时候，你可以移动到以下格子之一：
- 满足
j < k <= grid[i][j] + j的格子(i, k)（向右移动），或者- 满足
i < k <= grid[i][j] + i的格子(k, j)（向下移动）。请你返回到达 右下角 格子
(m - 1, n - 1)需要经过的最少移动格子数，如果无法到达右下角格子，请你返回-1。
2、接口描述
class Solution {
public:int minimumVisitedCells(vector<vector<int>>& grid) {}
};3、原题链接
2617. 网格图中最少访问的格子数
二、解题报告
1、思路分析
定义 f[i][j] 表示从 (i,j) 到 (m−1,n−1) 经过的最少格子数。
那么可以很容易的写出状态转移方程：
f[i][j] = min(f[i][j + k], f[i + k][j]) + 1，其中k <= grid[i][j]
这个状态转移方程是O(n+ m)的，那么有n * m个状态，总体时间复杂度就是O(n*m*(n+m))，显然会爆掉
那么如何优化呢？
状态数不好优化，那么从转移方程上入手，发现这个转移方程就是获取区间最值，那么我们有很多手段，这里选择使用树状数组，因为不好写错（
我们自底向上转移，即倒序遍历来转移，这样需要每一列开一个树状数组，然后行树状数组只开一个就行，因为我们是一行一行向上遍历
2、复杂度
时间复杂度： O(mnlog(m+n))空间复杂度：O(mn)
3、代码详解
void add(int x, int k, vector<int>& tr){for(; x < tr.size(); x += (x & -x))tr[x] = min(tr[x], k);
}
int query(int x, vector<int>& tr){int res = 1e8;for(; x; x &= (x - 1))res = min(res, tr[x]);return res;
}
class Solution {
public:int minimumVisitedCells(vector<vector<int>>& g) {int m = g.size(), n = g[0].size(), f = 1e8;vector<vector<int>> tr_col(n, vector<int>(m + 1, 1e8));for(int i = m - 1; i >= 0; i--){vector<int> tr_row(n + 1, 1e8);for(int j = n - 1; j >= 0; j--){f = 1e8;if(i == m - 1 && j == n - 1) f = 1;f = min(f, 1 + min(query(min(m, i + 1 + g[i][j]), tr_col[j]), query(min(n, j + 1 + g[i][j]), tr_row)));add(j + 1, f, tr_row), add(i + 1, f, tr_col[j]);cout << f << ' ';}}return f < 1e8 ? f : -1;}
};这篇关于树状数组优化dp，2617. 网格图中最少访问的格子数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
