LeetCode三则

三道动态规划

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int result = solution.uniquePaths(3, 2);
        System.out.println(result);

        result = solution.uniquePaths(7, 3);
        System.out.println(result);
    }

    /**
     * @author XiSoil
     * @date 2024/04/18 23:18
     *执行分布用时0ms,击败的100.00%Java用户
     *消耗内存分布33.98MB,击败的65.54%Java用户
     **/
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
解释：因为路径 1→3→5→2→1 的总和最小。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

public class Solution {
    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(new Solution().minPathSum(grid));

        grid = new int[][]{{1, 2, 3}, {4, 5, 6}};
        System.out.println(new Solution().minPathSum(grid));
    }

    /**
     * @author XiSoil
     * @date 2024/04/18 23:26
     *执行分布用时2ms,击败的94.88%Java用户
     *消耗内存分布44.30MB,击败的86.89%Java用户
     **/
    public int minPathSum(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 = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        return dp[m - 1][n - 1];
    }
}

740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。


提示：
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

public class Solution {
    public static void main(String[] args) {
        int[] nums = {3, 4, 2};
        System.out.println(new Solution().deleteAndEarn(nums));
        nums = new int[]{2, 2, 3, 3, 3, 4};
        System.out.println(new Solution().deleteAndEarn(nums));
    }
    /**
     * @author XiSoil
     * @date 2024/04/18 23:11
     *执行分布用时3ms,击败的52.91%Java用户
     *消耗内存分布44.61MB,击败的6.65%Java用户
     **/
    public int deleteAndEarn(int[] nums) {
        int[] earns = new int[10001];
        int maxNum = 0;
        for (int num : nums) {
            earns[num] += num;
            maxNum = Math.max(maxNum, num);
        }
        int[] earnList = new int[10001];
        earnList[0] = earns[0];
        earnList[1] = Math.max(earns[0], earns[1]);
        for (int i = 2; i <= maxNum; i++) {
            earnList[i] = Math.max(earnList[i-1],earns[i]+earnList[i-2]);
        }
        return earnList[maxNum];
    }
}