这周的日常

其实这周的任务也不是很重，小组这块主要就是改bug和算法的练习，算法自己写着是真的没有什么手感，这里面的题好多都是没有思路的，我也是想分享自己决定比较难的算法类型：

题目：在m*n的棋盘里每格一个礼物，每个礼物有价值（大于0）。你从棋盘左上角开始拿礼物，并每次往左和下移动一格，直到达到棋盘右下角。问最多拿多少价值的礼物？

解题思路：
        找某个位置的最大价值礼物，只要知道它的上面位置和左边位置的最大价值，再加上本身的价值，就能得出结果。递归可解。
几个注意点：
        1.递归替换成循环，和之前一样，减少重复计算。
解题步骤：
        先推递归式：f ( i , j ) = m a x ( f ( i , j − 1 ) , f ( i − 1 , j ) ) + g ( i , j ) f(i,j)=max(f(i,j-1),f(i-1,j))+g(i,j)f(i,j)=max(f(i,j−1),f(i−1,j))+g(i,j)，觉得不好看的话，就写个伪码吧f ( i , j ) = m a x ( l e f t , u p ) + g ( i , j ) f(i,j)=max(left, up)+g(i,j)f(i,j)=max(left,up)+g(i,j)，其中g(i,j)是位置本身礼物的价值，f(i,j)表示当前拿到的最大礼物的价值，别弄混了，然后遍历数组，算出每个位置的最大礼物价值，得到的价值用一个二维数组maxValues记录起来。
取出二维数组右下角的值即为答案。

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

我决定动态规划的变形有好多，也是见过几道，但是再看见还是不太清楚该怎么想，怎么去写，记录下来，以后可以回过来看

文章作者: Mr. Fortunate

文章链接: https://www.fortunate.cool/2022/08/06/%E8%BF%99%E5%91%A8%E7%9A%84%E6%97%A5%E5%B8%B8/

算法