314场周赛复盘

第四道

6203. 矩阵中和能被 K 整除的路径

dfs 必定超时

动态规划

确定状态（原问题和子问题变化的部分）：i，j, 从（0，0）到（i，j）路径和与k的余数也是一直变化的

确定dp数组的含义：dp[i][j][x]:从（0，0）到（i，j）路径和mod k ==x的数量

确定选择：向右，向下

我们要求：dp[m-1][n-1][0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private static final int V=7+1000*1000*1000;
    public int numberOfPaths(int[][] grid, int k) {
        int m=grid.length;
        int n=grid[0].length;
        int dp[][][]=new int[m][n][k];
        dp[0][0][grid[0][0] % k]=1;
        // 处理第0行
        int sum=grid[0][0]%k;
        for(int j=1;j<n;j++){
            dp[0][j][(sum+grid[0][j])%k]=dp[0][j-1][sum] %V;
            sum=(sum+grid[0][j])%k;
        }
        // 处理第0列
        sum=grid[0][0]%k;
        for(int i=1;i<m;i++){
            dp[i][0][(sum+grid[i][0])%k]=dp[i-1][0][sum] %V;
            sum=(sum+grid[i][0])%k;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                for(int x=0;x<k;x++){
                    dp[i][j][(x+grid[i][j])%k]=(dp[i-1][j][x]+dp[i][j-1][x])%V;
                }
            }
        }
        return dp[m-1][n-1][0];
    }
}

类似的题目

力扣第 64 题「 最小路径和」

求解到达最右下方经过的路径和最小。

dp[i][j]:从（0，0）到（i，j）路径和最小的值

状态转移方程 dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]

174. 地下城游戏

dp[i][j]:表示从(0,0)到（i，j）需要的最低初始健康点数

难点：「到达 A 的最小生命值」不能由「到达 B 的最小生命值」和「到达 C 的最小生命值」推导出来

image-20221011091815457

因为：到达B，到达C的生命值是不知道的

所以，上面的dp定义不对

**==反向思考==**： 这题非常好

dp[i][j]:从(m-1,n-1)到（i，j）需要的最低初始健康点数

边界：

dp[m-1][i]=dungeon[m-1][i]>=dp[m-1][i+1] ? 1:dp[m-1][i+1]-dungeon[m-1][i];

状态转移方程：

1
2
int temp=Math.min(dp[i+1][j],dp[i][j+1]);
dp[i][j]= dungeon[i][j]>temp? 1: temp-dungeon[i][j];

第三道

2434. 使用机器人打印字典序最小的字符串

关键在于：什么时候出栈

当该栈顶元素比后序元素都小于等于时出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String robotWithString(String s) {
        Stack<Character> stack = new Stack<Character>();
        int[] nums=new int[26];
        char[] str=s.toCharArray();
        for(char c:str){
            nums[c-'a']++;
        }
        StringBuilder sb=new StringBuilder();
        for(char c:str){
            
            stack.push(c);
            nums[c-'a']--;
        
            // 判断是否需要弹出
            while(!stack.isEmpty() && isSmall(nums,c)){  // 当前栈顶元素比后序元素都要小于等于
                sb.append(stack.pop());
                if(!stack.isEmpty()){
                    c=stack.peek();
                }
            }
        }
        return sb.toString();
    }
    public boolean isSmall(int nums[],char c){
        int len =c-'a';
        for(int i=0;i<len;i++){
            if(nums[i]>0){
                return false;
            }
        }
        return true;
    }
}

类似的题

给定长度为 N 的字符串 S，要构造一个长度为 N 的字符串 T。起初，T 是一个空串，随后反复执行下列两个操作中的任意一个，最终目标是构造字典序尽可能小的字符串 T。

操作一：从 S 的头部取一个字符，加到 T 的尾部。

操作二：从 S 的尾部取一个字符，加到 T 的尾部。

例如：输入 N=6，S=ACDBCB；构造的 T=ABCBCD

这题简单多了：双指针就可以