Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 3070. Count Submatrices with Top-Left Element and Sum Less Than k

---

參考資訊：
https://algo.monster/liteproblems/3070
https://algorithm.lomtom.cn/leetcode/count-submatrices-with-top-left-element-and-sum-less-than-k

題目：


方法：

Dynamic Programming

解答：

int countSubmatrices(int** grid, int gridSize, int* gridColSize, int k)
{
    int i = 0;
    int j = 0;
    int r = 0;
    int row_size = gridSize;
    int col_size = gridColSize[0];
    int** sum = calloc(sizeof(int *), row_size + 1);

    for (i = 0; i <= row_size; i++) {
        sum[i] = calloc(sizeof(int), col_size + 1);
    }

    for (i = 1; i <= row_size; i++) {
        for (j = 1; j <= col_size; j++) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
            sum[i][j] -= sum[i - 1][j - 1];
            sum[i][j] += grid[i - 1][j - 1];

            if (sum[i][j] <= k) {
                r += 1;
            }
        }
    }

    return r;
}