LeetCode第297场周赛

• 5259. 计算应缴税款总额
• • 题目
  • 解法：模拟
• 5270. 网格中的最小路径代价
• • 题目
  • 解法：动态规划
• 5289. 公平分发饼干
• • 题目
  • 解法：回溯
• 6094. 公司命名
• • 题目
  • 解法：分组+哈希

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double res = 0;        
        int n = brackets.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && brackets[i - 1][0] >= income) {
                break;
            }            
            int upper = brackets[i][0], percent = brackets[i][1];            
            int money = 0;
            if (i == 0) {
                money = Math.min(upper, income);
            } else {                
                money = Math.min(income - brackets[i - 1][0], upper - brackets[i - 1][0]);                
            }
            res += money * percent;
        }
        return res / 100;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)， n = b r a c k e t s . l e n g t h n=brackets.length n=brackets.length
• 空间复杂度： O ( 1 ) O(1) O(1)

• 状态定义

d p [ i ] [ j ] dp[i][j] dp[i][j]：表示从第一行任意单元格出发，到达单元格 ( i , j ) (i,j) (i,j)的最小路径代价（ 0 ≤ i ≤ m 0 le i le m 0≤i≤m， 0 ≤ j ≤ n 0 le j le n 0≤j≤n）

• 初始条件

d p [ 0 ] [ j ] = g r i d [ 0 ] [ j ] dp[0][j] = grid[0][j] dp[0][j]=grid[0][j]（ 0 ≤ j ≤ n 0 le j le n 0≤j≤n）

• 状态转移

在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格，到达单元格 ( i , j ) (i,j) (i,j)的最小路径有可能是从 上一行 的某一个单元格转移而来，因此需遍历 上一行 单元格寻找最小路径，状态转移方程如下：

d p [ i ] [ j ] = M a t h . m i n ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] + g r i d [ i ] [ j ] + m o v e C o s t [ g r i d [ i − 1 ] [ k ] ] [ j ] ) dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + grid[i][j] + moveCost[grid[i-1][k]][j]) dp[i][j]=Math.min(dp[i][j],dp[i−1][k]+grid[i][j]+moveCost[grid[i−1][k]][j])（ 0 ≤ k ≤ n 0 le k le n 0≤k≤n）

• 最终结果

题目要求：从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。

因此遍历 d p [ m − 1 ] [ j ] dp[m-1][j] dp[m−1][j]（ 0 ≤ j ≤ n 0le j le n 0≤j≤n），最小值即为所求

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        // 状态定义
        int[][] dp = new int[m][n];
        // 初始化
        for (int j = 0; j < n; j++) {
            dp[0][j] = grid[0][j];
        }        
        // 状态转移
        for (int i = 1; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + grid[i][j] + moveCost[grid[i-1][k]][j]);
                }
            }
        }
        // 最终结果
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            res = Math.min(res, dp[m - 1][j]);
        }
        return res;
    }
}

• 时间复杂度： O ( m × n 2 ) O(m times n^2) O(m×n2)， m = g r i d . l e n g t h m = grid.length m=grid.length， n = g r i d [ 0 ] . l e n g t h n = grid[0].length n=grid[0].length

• 空间复杂度： O ( m × n ) O(mtimes n) O(m×n)

• LeetCode 5289. 公平分发饼干(集合划分问题/回溯)

• LeetCode 6094. 公司命名(分组+哈希)