[英雄星球六月集训LeetCode解题日报] 第28日 动态规划

日报

题目

一、 2310. 个位数字为 K 的整数之和

链接: 2310. 个位数字为 K 的整数之和

1. 题目描述

2310. 个位数字为 K 的整数之和

难度：中等

给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：

• 每个整数个位数字都是 k 。
• 所有整数之和是 num 。

返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。

注意：

• 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
• 个位数字 是数字最右边的数位。

示例 1：

输入：num = 58, k = 9
输出：2
解释：
多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。

1
2
3
4
5
6
7

示例 2：

输入：num = 37, k = 2
输出：-1
解释：个位数字为 2 的整数无法相加得到 37 。
1
2
3

示例 3：

输入：num = 0, k = 7
输出：0
解释：空多重集的和为 0 。

1
2
3
4

提示：

• 0 <= num <= 3000
• 0 <= k <= 9

2. 思路分析

这是前两周周赛题目[LeetCode周赛复盘] 第 298 场周赛20220619

• 因为数字任选，因此我们用个位数乘倍数找复合的尾数即可，这个倍数就是答案。
• 先做一遍乘法表，记下k的倍数中，目标尾数出现时最少要乘几。
• 最后如果num小于这个倍数*k，那么是不行的。
• 如果num大于等于倍数*k，则k可以任意调整十位数百位数，一定可以满足题意。

3. 代码实现

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        w = num%10
        cnt = defaultdict(lambda :10**9)  # k的倍数尾数最小倍数
        min_mul = defaultdict(lambda :10**9)
        for i in range(1,11):
            wei = k*i%10
            cnt[wei] = min(cnt[wei],i)
            min_mul[wei] = min(min_mul[wei],k*i)
        if w not in cnt:
            return -1
        if num < k * cnt[w]:
            return -1
        return cnt[w]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、 1594. 矩阵的最大非负积

链接: 1594. 矩阵的最大非负积

1. 题目描述

1594. 矩阵的最大非负积

难度：中等

给你一个大小为 rows x cols 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (rows - 1, cols - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为负数，则返回 -1 。

**注意，**取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],
             [-2,-3,-3],
             [-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1

1
2
3
4
5
6

示例 2：

输入：grid = [[1,-2,1],
             [1,-2,1],
             [3,-4,1]]
输出：8
解释：最大非负积对应的路径已经用粗体标出 (1 * 1 * -2 * -4 * 1 = 8)

1
2
3
4
5
6

示例 3：

输入：grid = [[1, 3],
             [0,-4]]
输出：0
解释：最大非负积对应的路径已经用粗体标出 (1 * 0 * -4 = 0)

1
2
3
4
5

示例 4：

输入：grid = [[ 1, 4,4,0],
             [-2, 0,0,1],
             [ 1,-1,1,1]]
输出：2
解释：最大非负积对应的路径已经用粗体标出 (1 * -2 * 1 * -1 * 1 * 1 = 2)

1
2
3
4
5
6

提示：

• 1 <= rows, cols <= 15
• -4 <= grid[i][j] <= 4

2. 思路分析

• 上来就dp，一运行发现错了。
• 发现数组里有负数，而乘负数会起到翻转的作用，也就是最小可能会变成最大。
• 那么我们dp时储存一个最小一个最大，状态转移时选择即可。

3. 代码实现

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        MOD = 10**9+7
        m,n = len(grid),len(grid[0])
        @cache
        def dfs(i,j):
            # 返回最大最小积
            if i == 0 and j == 0:                
                return grid[0][0],grid[0][0]
            if i == 0:
                a,b = dfs(i,j-1)
                return a*grid[i][j],b*grid[i][j]
            if j == 0:
                a,b = dfs(i-1,j)
                return a*grid[i][j],b*grid[i][j]
            a,b = dfs(i-1,j)
            c,d = dfs(i,j-1)
            a*=grid[i][j]
            b*=grid[i][j]
            c*=grid[i][j]
            d*=grid[i][j]
            # print(a,b,c,d)
            return min(a,b,c,d),max(a,b,c,d)
        ret = dfs(m-1,n-1)[1]
        return ret%MOD if ret >= 0 else -1
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

参考链接

• 链接: [LeetCode周赛复盘] 第 298 场周赛20220619