标签： 动态规划

目标

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

说明：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

思路

有一个由多行数字排列组成的三角形，每一行比上一行多一个数字，当前数字可以到达下一行下标相同或者下标 +1 的两个数字，求从第一行到最后一行的路径中数字和的最小值。

定义 dp[i][j] 表示从第 i 行 j 列到达底部的最小路径和。dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row[i][j]。

代码

/**
 * @date 2024-08-06 15:42
 */
public class MinimumTotal120 {

    public int minimumTotal_new(List<List<Integer>> triangle) {
        int n = triangle.size();
        int m = triangle.get(n - 1).size();
        int[] dp = new int[m];
        for (int i = 0; i < m; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            List<Integer> row = triangle.get(i);
            int l = row.size();
            for (int j = 0; j < l; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
            }
        }
        return dp[0];
    }

}

性能

目标

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

说明：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

思路

在第 1 天有一个人发现了一个秘密，每一个新知道秘密的人在 delay 天之后的 每一天 会向一个 新人 分享这个秘密，每一个人在知道秘密之后的 forget 天会忘记秘密，求第 n 天结束时知道秘密的人数。

定义 dp[i] 表示在第 i 天 新增 知道秘密的人数，它等于超过了延迟 delay 并且还没有忘记的人数总和，也即 [i - forget + 1, i - delay] 之间的新增人数总和，求和可以使用前缀和优化。

代码

/**
 * @date 2025-09-09 8:57
 */
public class PeopleAwareOfSecret2327 {

    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int[] dp = new int[n + 1];
        int mod = 1000000007;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = Math.max(0, i - forget + 1); j <= Math.max(0, i - delay); j++) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
        int res = 0;
        for (int i = Math.max(0, n - forget + 1); i <= n; i++) {
            res = (res + dp[i]) % mod;
        }
        return res;
    }

}

性能

目标

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

说明：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

思路

统计 m x n 矩阵中 全是 1 的正方形子矩阵个数。

遍历的逻辑是枚举长度，以左上顶点为圆心，长度为半径进行遍历。

代码

/**
 * @date 2025-08-20 8:44
 */
public class CountSquares1277 {

    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 1) {
                    continue;
                }
                int max = Math.min(m - i, n - j);
                int l = 1;
                here:
                for (; l < max; l++) {
                    for (int y = i + l; y >= i; y--) {
                        if (matrix[y][j + l] == 0) {
                            break here;
                        }
                    }
                    for (int x = j + l; x >= j; x--) {
                        if (matrix[i + l][x] == 0) {
                            break here;
                        }
                    }
                }
                res += l;
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums 和一个 正 整数 k 。

nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

• (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

返回 nums 的 最长有效子序列 的长度。

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：
最长有效子序列是 [1, 2, 3, 4, 5] 。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：
最长有效子序列是 [1, 4, 1, 4] 。

说明：

• 2 <= nums.length <= 10^3
• 1 <= nums[i] <= 10^7
• 1 <= k <= 10^3

思路

找出数组 nums 的有效子序列的最大长度，有效子序列指相邻元素之和模 k 的值相等。

3201.找出有效子序列的最大长度I 是本题 k = 2 的特例。这个题目可能的组合有 k^2 种。

定义 dp[i][j] 表示子序列后两项模 k 的值为 i 和 j 的子序列长度。

代码

/**
 * @date 2025-07-16 10:18
 */
public class MaximumLength3202 {

    public int maximumLength(int[] nums, int k) {
        int[][] dp = new int[k][k];
        int res = 0;
        for (int num : nums) {
            int m = num % k;
            for (int i = 0; i < k; i++) {
                dp[i][m] = dp[m][i] + 1;
                res = Math.max(res, dp[i][m]);
            }
        }
        return res;
    }

}

性能