动态规划算法之矩阵前缀和

function calculatePrefixSum(matrix) {  
    const rows = matrix.length;  
    const cols = matrix[0].length;  
    const prefixSum = new Array(rows + 1);  
  
    // 初始化前缀和数组的第一行和第一列  
    for (let i = 0; i <= rows; i++) {  
        prefixSum[i] = new Array(cols + 1).fill(0);  
    }  
  
    // 计算前缀和  
    for (let i = 1; i <= rows; i++) {  
        for (let j = 1; j <= cols; j++) {  
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];  
        }  
    }  
  
    return prefixSum;  
}  
  
function sumSubmatrix(prefixSum, x1, y1, x2, y2) {  
    return prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1];  
}  
  
// 示例用法  
const matrix = [  
    [1, 2, 3],  
    [4, 5, 6],  
    [7, 8, 9]  
];  
  
const prefixSum = calculatePrefixSum(matrix);  
const x1 = 1, y1 = 1, x2 = 2, y2 = 2;  
const sum = sumSubmatrix(prefixSum, x1, y1, x2, y2);  
  
console.log(`子矩阵(${x1}, ${y1}) 到 (${x2}, ${y2}) 的和: ${sum}`);