LeetCode?動態(tài)規(guī)劃之矩陣區(qū)域和詳情

更新時間：2022年04月22日 10:41:17 作者：心城以北

這篇文章主要介紹了LeetCode?動態(tài)規(guī)劃之矩陣區(qū)域和詳情，文章基于Java的相關(guān)資料展開對LeetCode?動態(tài)規(guī)劃的詳細(xì)介紹，需要的小伙伴可以參考一下

題目

矩陣區(qū)域和

給你一個 m x n 的矩陣 mat 和一個整數(shù) k ，請你返回一個矩陣 answer ，其中每個 answer[i][j] 是所有滿足下述條件的元素 mat[r][c] 的和：

i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩陣內(nèi)。

示例 1：

輸入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
輸出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

輸入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
輸出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

m ==?mat.length
n ==?mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

題解

解題分析

解題思路：

本題是以典型的動態(tài)規(guī)劃問題；
獲取前綴矩陣dp[][]

dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];

根據(jù)前綴矩陣計算結(jié)果：

核心問題轉(zhuǎn)化為了：1).求這兩個過程的轉(zhuǎn)移方程；2). 邊界處理.

解題代碼如下所示：

復(fù)雜度

時間復(fù)雜度： O(M * N)
空間復(fù)雜度： O(M * N)

解題代碼

題解代碼如下（代碼中有詳細(xì)的注釋說明）：

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length,n = mat[0].length;
        int[][] dp = get_dp(mat,m,n);
        return get_res(dp,m,n,k);
    }
    //獲取dp數(shù)組
    public int[][] get_dp(int[][] arr,int m,int n){
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
        return dp;
    }
    //獲取結(jié)果
    public int[][] get_res(int[][] dp,int m,int n,int k){
        int[][] res = new int[m][n];
        int x1,y1,x2,y2;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                x1 = Math.max(0,i-k);y1 = Math.max(0,j-k);
                x2 = Math.min(m,i+k+1);y2 = Math.min(n,j+k+1);
                res[i][j] = dp[x2][y2]-dp[x1][y2]-dp[x2][y1]+dp[x1][y1];
            }
        }
        return res;
    }
}

提交后反饋結(jié)果（由于該題目沒有進(jìn)行優(yōu)化，性能一般）：