easy understand dp solution


  • 0
    S
    public class NumMatrix {
    	int[][] dp;
    	public NumMatrix(int[][] matrix) {
    		dp = matrix;
    		for (int i = 0; i < dp.length; i++) {
    			for (int j = 0; j < dp[0].length; j++) {
    				if (i >0) dp[i][j] += dp[i-1][j];
    	                	if (j >0) dp[i][j] += dp[i][j-1];
    	                	if (i> 0 && j > 0) dp[i][j] -= dp[i-1][j-1];
    			}
    		}
    	}
    	    
    	public int sumRegion(int row1, int col1, int row2, int col2) {
    	        int res = dp[row2][col2];
    	        if (row1 >0) res -= dp[row1-1][col2];
    	        if (col1 >0) res -= dp[row2][col1-1];
    	        if (row1 > 0 && col1 > 0) res += dp[row1-1][col1-1];
    	        return res;
    	}
    }
    

Log in to reply
 

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