題目

給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j (i ≤ j) 范圍內(nèi)元素的總和，包含 i, j 兩點(diǎn)。

示例：

給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數(shù)為 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
說明:

你可以假設(shè)數(shù)組不可變。
會(huì)多次調(diào)用 sumRange 方法。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/range-sum-query-immutable
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法1：動(dòng)態(tài)規(guī)劃

class NumArray {
    int[] nums=null;
    int sum=0;
    int[] dp=null;
    public NumArray(int[] nums) {
        this.nums=nums;
        int[] dp=new int[nums.length+1];
        dp[0]=0;
        for(int i = 1 ; i< nums.length+1;i++){
            sum+=nums[i-1];
            dp[i]=sum;
        }
        this.dp=dp;
    }
    
    public int sumRange(int i, int j) {
        return (dp[j+1]-dp[i]);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

秀到了，原來是這樣玩的，暴力法時(shí)間復(fù)雜度高是因?yàn)橐恢敝貜?fù)運(yùn)算，而動(dòng)態(tài)規(guī)劃的話強(qiáng)在把他們的求和都記下來，只需要利用數(shù)學(xué)知識(shí)相減就可以了。