当前位置：首页 > news >正文

网站模板怎么设计软件怎样和政府交换友链

news 2025/7/29 18:40:51

网站模板怎么设计软件,怎样和政府交换友链,xrea WordPress限制,哪些网站可以免费做推广呢一、需求在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值&a…

一、需求

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:输入: 
[[1,3,1],[1,5,1],[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

二、动态规划

2.1 思路分析

题目要求计算礼物的最大价值，涉及到"最大"，考虑使用动态规划解决；
那么就需要定义状态，定义dp[i][j]为从左上角到单元格(i,j)礼物的最大累计价值；
当i == 0且j == 0时，初始化状态为dp[0][0] = grid[0][0]；
当i == 0且j != 0时，这是数组第一行，只能从左向右到达单元格(i,j)，则dp[i][j] = dp[i][j-1] + grid[i][j]；
当i != 0且j == 0时，这是数组第一列，只能从上向下到达单元格(i,j)，则dp[i][j] = dp[i-1][j] + grid[i][j]；
当i != 0且j != 0时，可以从左到右或者从上到下到达单元格(i,j)，dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + grid[i][j]；

2.2 代码实现

class Solution {public int maxValue(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(i == 0 && j == 0) continue;else if(i == 0) {dp[i][j] = dp[i][j-1] + grid[i][j];} else if(j == 0) {dp[i][j] = dp[i-1][j] + grid[i][j];} else {dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]) + grid[i][j];}}}return dp[m-1][n-1];}
}

2.3 复杂度分析

时间复杂度为O(MN)，即遍历数组的次数；
空间复杂度为O(MN)，dp数组占用MN大小的额外空间；

三、动态规划优化1

3.1 思路分析

因为dp[i][j]只与dp[i][j-1]、dp[i-1][j]及grid[i][j]有关，因此通过在grid数组上修改来避免dp数组申请空间，从而使空间复杂度降至O(1)；

3.2 代码实现

class Solution {public int maxValue(int[][] grid) {int m = grid.length;int n = grid[0].length;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(i == 0 && j == 0) continue;else if(i == 0) {grid[i][j] = grid[i][j-1] + grid[i][j];} else if(j == 0) {grid[i][j] = grid[i-1][j] + grid[i][j];} else {grid[i][j] = Math.max(grid[i][j-1],grid[i-1][j]) + grid[i][j];}}}return grid[m-1][n-1];}
}

四、动态规划优化2

4.1 思路分析

上述代码仍然可以优化，当grid数组很大时，i = 0 或 j = 0的情况仅占少数，这样每次循环都会冗余一次判断，因此可以先初始化矩阵的第一行和第一列，然后再遍历递推；

4.2 代码实现

class Solution {public int maxValue(int[][] grid) {int m = grid.length;int n = grid[0].length;//初始化第一列和第一行for(int i = 1; i < m; i++) {grid[i][0] = grid[i-1][0] + grid[i][0];}for(int j = 1; j < n; j++) {grid[0][j] = grid[0][j-1] + grid[0][j];}//递归其余行列for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {grid[i][j] = Math.max(grid[i][j-1],grid[i-1][j]) + grid[i][j];}}return grid[m-1][n-1];}
}