如何实现二维矩阵的对角线遍历填充（非行/列优先）

下面针对两种常见的对角线填充场景，给出具体的循环实现代码：

场景1：按子问题长度递增填充（区间DP常用） #

这种方式适用于区间类DP问题（比如最长回文子串、矩阵链乘法），先填充所有长度为1的子问题（主对角线），再依次填充长度更长的对角线，直到覆盖整个矩阵。

Python 代码 #

n = 5  # 矩阵的边长
dp = [[0] * n for _ in range(n)]

# 按子问题长度从1到n遍历
for length in range(1, n + 1):
    # 遍历当前长度下所有合法的起始行i
    for i in range(n - length + 1):
        j = i + length - 1  # 对应对角线的列索引
        # 在这里编写你的DP状态转移逻辑
        dp[i][j] = 你的计算值

C++ 代码 #

int n = 5;
vector<vector<int>> dp(n, vector<int>(n, 0));

// 遍历子问题长度，从1到n
for (int length = 1; length <= n; ++length) {
    // 遍历当前长度对应的所有起始行
    for (int i = 0; i <= n - length; ++i) {
        int j = i + length - 1;
        // 写入DP状态转移逻辑
        dp[i][j] = /* 你的计算逻辑 */;
    }
}

场景2：右上→左下方向填充对角线 #

如果需要从矩阵右上角开始，依次向左下方向填充每条对角线（比如某些二维DP问题需要依赖右上角/右下角的状态），可以用偏移量遍历的方式：

Python 代码 #

n = 5
dp = [[0] * n for _ in range(n)]

# 遍历所有可能的偏移量，覆盖所有右上→左下的对角线
for offset in range(2 * n - 1):
    # 确定当前对角线的行索引范围
    start_i = max(0, offset - (n - 1))
    end_i = min(offset, n - 1)
    for i in range(start_i, end_i + 1):
        j = offset - i
        if 0 <= j < n:
            # 编写DP状态转移逻辑
            dp[i][j] = 你的计算值

C++ 代码 #

int n = 5;
vector<vector<int>> dp(n, vector<int>(n, 0));

// 遍历偏移量，覆盖所有右上→左下的对角线
for (int offset = 0; offset < 2 * n - 1; ++offset) {
    int start_i = max(0, offset - (n - 1));
    int end_i = min(offset, n - 1);
    for (int i = start_i; i <= end_i; ++i) {
        int j = offset - i;
        if (j >= 0 && j < n) {
            // 写入DP状态转移逻辑
            dp[i][j] = /* 你的计算逻辑 */;
        }
    }
}

根据你的DP问题依赖关系，选择对应的填充方式即可。

内容的提问来源于stack exchange，提问作者Harsh Anmol