thảo luận Leetcode mỗi ngày

class Solution {
    public int maxMoves(int[][] grid) {
        int height = grid.length;
        int width  = grid[0].length;

        int[][] dp = new int[height][width];
        for (int i = 0; i < height; i++) {
            Arrays.fill(dp[i], 1);
        }
        int[][] direction = new int[][]{
            {-1, 1},
            {0, 1},
            {1, 1}
        };
        int ROW = 0;
        int COL = 1;

        int longestDistance = 0;
        for (int c = width - 2; c >= 0; c--) {
            for (int r = 0; r < height; r++) {
                for (int[] dir : direction) {
                    if (isOutOfRange(r + dir[ROW], 0, height) || isOutOfRange(c + dir[COL], 0, width)) {
                        continue;
                    }

                    if (grid[r][c] < grid[r + dir[ROW]][c + dir[COL]]) {
                        dp[r][c] = Math.max(
                            dp[r][c],
                            dp[r + dir[ROW]][c + dir[COL]] + 1
                        );
                        if (c == 0) {
                            longestDistance = Math.max(
                                longestDistance,
                                dp[r][c] - 1
                            );
                        }
                    }
                }
            }
        }

        return longestDistance;
    }

    public boolean isOutOfRange(int cur, int min, int max) {
        return cur < min || cur >= max;
    }
}

class Solution {
    int[][] memoi, grid;
    int m, n;
    int[] dy = {-1, 0, 1};
    public int maxMoves(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.memoi = new int[m][n];

        int res = 1;
        for (int i = 0; i < m; i++) {
            res = Math.max(res, dp(i, 0));
        }

        return res - 1;
    }

    private int dp(int row, int col) {
        if (col == n - 1) {
            return 1;
        }

        if (memoi[row][col] != 0) {
            return memoi[row][col];
        }

        int res = 0;
        for (int i = 0; i < 3; i++) {
            int ny = row + dy[i], nx = col + 1;

            if (ny < 0 || ny == m || nx < 0 || nx == n ||
                grid[ny][nx] <= grid[row][col]) {
                continue;
            }

            res = Math.max(res, dp(ny, nx));

        }

        return memoi[row][col] = 1 + res;
    }
}

impl Solution {
    pub fn max_moves(grid: Vec<Vec<i32>>) -> i32 {
        let (m, n) = (grid.len(), grid[0].len());
        let (mut memo, mut memo_prev) = (vec![0; m], vec![0; m]);

        let mut result = 0;
        for j in 0..(n - 1) {
            for i in 0..m {
                if j > 0 && memo_prev[i] == 0 {
                    continue;
                }

                if i > 0 && grid[i][j] < grid[i - 1][j + 1] {
                    memo[i - 1] = memo[i - 1].max(memo_prev[i] + 1);
                    result = result.max(memo[i - 1]);
                }

                if grid[i][j] < grid[i][j + 1] {
                    memo[i] = memo_prev[i].max(memo_prev[i] + 1);
                    result = result.max(memo[i]);
                }

                if i < m - 1 && grid[i][j] < grid[i + 1][j + 1] {
                    memo[i + 1] = memo[i + 1].max(memo_prev[i] + 1);
                    result = result.max(memo[i + 1]);
                }
            }

            (memo, memo_prev) = (memo_prev, memo);
            memo.iter_mut().for_each(|cell| *cell = 0);
        }

        result
    }
}

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        vector<int> dp(grid.size(), 0);
        vector<int> next_dp(grid.size(), 0);
        int ret = 0;
        for (int j = 1; j < grid[0].size(); ++j) {
            for (int i = 0; i < grid.size(); ++i) {
                for (int x = max(0, i - 1); x <= min((int)grid.size() - 1, i + 1); ++x) {
                    if (grid[x][j-1] < grid[i][j]) next_dp[i] = max(next_dp[i], dp[x] + 1);
                }
                ret = max(ret, next_dp[i]);
            }
            if (ret < j) break;
            fill(dp.begin(), dp.end(), 0);
            dp.swap(next_dp);
        }
        return ret;
    }
};

public class Solution
{
    int[][] dirs = [[-1, -1], [0, -1], [1, -1]];
    public int MaxMoves(int[][] grid)
    {
        int rows = grid.Length;
        int cols = grid[0].Length;

        int[,] dp = new int[rows, cols];
        for (int i = 0; i < rows; i++)
        {
            dp[i, 0] = 1;
        }

        int result = 1;
        for (int col = 1; col < cols; col++)
        {
            for (int row = 0; row < rows; row++)
            {
                int localMax = 0;
                int current = grid[row][col];
                foreach (var dir in dirs)
                {
                    int r = row + dir[0];
                    int c = col + dir[1];
                    if (r < 0 || rows <= r || c < 0 || cols <= c)
                    {
                        continue;
                    }
                    if (dp[r,c] == 0 || current <= grid[r][c])
                    {
                        dp[row,col] = 0;
                        continue;
                    }
                    localMax = Math.Max(localMax, dp[r,c] + 1);
                }
                dp[row,col] = localMax;
                result = Math.Max(result, localMax);
            }
        }

        return result - 1;
    }
}