JAVA-------Easy Version To Understand!!!!!!


  • 0
    H
    	int[][] matrix;
    int[][] dp;
    
    public NumMatrix(int[][] matrix) {
    	if (matrix == null || matrix.length == 0)
    		return;
    	this.matrix = matrix;
    	int rows = matrix.length, colunms = matrix[0].length, sum = 0;
    	dp = new int[rows][colunms];
    
    	for (int i = 0; i < rows; i++) {
    		dp[i][0] = sum + matrix[i][0];
    		sum = sum + matrix[i][0];
    	}
    	sum = matrix[0][0];
    	for (int i = 1; i < colunms; i++) {
    		dp[0][i] = sum + matrix[0][i];
    		sum = sum + matrix[0][i];
    	}
    
    	for (int i = 1; i < rows; i++)
    		for (int j = 1; j < colunms; j++)
    			dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i][j];
    
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
    	if (row1 == 0 && col1 == 0)
    		return dp[row2][col2];
    	else if (row1 == 0)
    		return dp[row2][col2] - dp[row2][col1 - 1];
    	else if (col1 == 0)
    		return dp[row2][col2] - dp[row1 - 1][col2];
    	else if (row1 >= 1 && col1 >= 1)
    		return dp[row2][col2] - dp[row2][col1 - 1] - dp[row1 - 1][col2] + dp[row1 - 1][col1 - 1];
    	return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.