[leetcode] 304. Range Sum Query 2D - Immutable

class NumMatrix {
public:
    vector<vector<int>> dp;
    NumMatrix(vector<vector<int>>& matrix) {
        dp.assign(matrix.size(), vector<int>(matrix[0].size(), 0));
        
        for(int i = 0; i<matrix.size(); i++){
            for(int j = 0; j<matrix[0].size(); j++){
                
                
                dp[i][j] = (i - 1 >= 0 ? dp[i - 1][j] : 0) 
                         + (j - 1 >= 0 ? dp[i][j - 1] : 0)
                         - ((i - 1 >= 0 && j - 1 >= 0) ? dp[i - 1][j - 1] : 0)
                         + matrix[i][j];
            }
        }        
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {

        return dp[row2][col2]
            - (row1 - 1 >= 0 ? dp[row1 - 1][col2] : 0)
            - (col1 - 1 >= 0 ? dp[row2][col1 - 1] : 0)
            + ((row1 - 1 >= 0 && col1 - 1>= 0) ? dp[row1 - 1][col1 - 1] : 0);
    }
};

아주 단순한 dp문제입니다.

2차원 배열에서 각 칸까지의 직사각형의 합을 저장해두고

나중에 결과출력할떄 써먹으면 됩니다.

 

이정도 실행속도면 거이 최적의 해로 보입니다.

시간복잡도 o(n)