js网格图从左上到右下最小和,可以上下左右移动
时间: 2024-09-15 09:09:24 浏览: 35
在JavaScript中,创建网格图并计算从左上角到右下角的最小和通常涉及到动态规划或者深度优先搜索(DFS)。网格图通常是一个二维数组,每个元素代表一个格子的值。为了找到从左上角到右下角的路径,我们需要遍历每一个节点,并考虑当前节点加上相邻节点的值(如果有权限走那条路)。
假设我们有一个二维数组grid,其中每个元素grid[i][j]表示位置(i, j)的值,我们可以用以下步骤实现:
1. 初始化两个变量:startSum存储左上角的值,minPathSum初始设为无穷大。
2. 定义一个函数dfs(grid, i, j, startSum),用于递归地查找路径和:
- 如果i和j越界,返回0;
- 如果当前位置等于起点,直接返回startSum;
- 否则,尝试向四个方向(上、下、左、右)移动,更新pathSum为当前位置值加上对应方向邻居的dfs结果,然后取最小值。
```javascript
function minPathSum(grid, startRow, startCol) {
const rows = grid.length;
const cols = grid[0].length;
let dp = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
dp[startRow][startCol] = grid[startRow][startCol];
for (let i = 1; i < rows; i++) {
dp[i][startCol] = dp[i - 1][startCol] + grid[i][startCol];
}
for (let j = 1; j < cols; j++) {
dp[startRow][j] = dp[startRow][j - 1] + grid[startRow][j];
}
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[rows - 1][cols - 1];
}
```
阅读全文