DP動態規劃 深入淺出 以Range Sum Query Immutable 區間和 為例

題目敘述

在學習過比較基本的DP模型 費式數列、爬樓梯、找零錢...等之後，來看一個比較進階而且實用的DP模型，前綴和(Prefix sum)，可以再加以延伸推廣，來計算 區間和(Range Sum)。

詳細的題目可在這裡看到

題目會給定一個輸入陣列，並且定義好function界面，要求我們實作出sumRange(left, right) 區間和的功能。

測試範例

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

約束條件

Constraints:

• 1 <= nums.length <= 10^4

輸入陣列長度介於1 ~ 10^4 之間。

• -10^5 <= nums[i] <= 10^5

每個陣列元素界於 -10^5 ~ 10^5 之間。

• 0 <= left <= right < nums.length

動態測試給的區間一定是合法區間。

• At most 10^4 calls will be made to sumRange.

動態測試時，最多有10^4次函式呼叫。

同樣地，先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。

定義狀態 [我在哪裡]

我們可以透過前綴和Prefix sum，來間接求出 區間和Range sum

令PrefixSum[0] = nums[0]

PrefixSum[i] = nums[0] + nums[1] + ... +nums[i]　從第０項～第i項的總和

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

PrefixSum　前綴和本身的狀態轉移如下

PrefixSum[i]

= nums[0] + nums[1] + ... +nums[i]　從第０項～第i項的總和

= PrefixSum[i-1] +nums[i]

= [ 從第０項～第(i-1)項的總和 ]＋第ｉ項

= 從第０項～第i項的總和

接著，可以根據定義推導出

RangeSum(left, right) 區間［left, right］的元素總和

= PrefixSum( right ) - PrefixSum( left - 1 )

= nums[left] + nums[left+1] + ... + nums[right]

請留意邊界索引的處理！

3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]

PrefixSum 前綴和的初始條件就是第０項 = PrefixSum[0] = nums[0]

RangeSum 區間和呢？

類似的，邊界條件也發生在left = 0的時候，這時候左邊已經沒有別的元素了，

此時，PrefixSum[right] = RangeSum(left, right)

直接返回　PrefixSum[right] 即可

程式碼

class NumArray:

　def __init__(self, nums: List[int]):
　　
　　self.size = len(nums)
　　

　　# build prefix sum table when input nums is valid
　　self.s = [ 0 for _ in range(self.size) ]

　　self.s[0] = nums[0]

　　# s[k] = nums[0] + ... + nums[k]
　　# s[k] = s[k-1] + nums[k]
　　for k in range(1,self.size):
　　　self.s[k] = self.s[ k-1 ] + nums[ k ]
　　

　def sumRange(self, left: int, right: int) -> int:
　　

　　# lookup table from prefix sum table, s
　　if left == 0:
　　　return self.s[ right ]
　　else:
　　　return self.s[ right ]-self.s[ left-1 ]

複雜度分析

時間複雜度：

O( n ) : init() 初始化的時候，需要計算PrefixSum的表格
O( 1 ) : sumRange(left, right)，直接查表，做個減法，就可以得到區間和的答案。

空間複雜度：

O( n ) : init() 初始化的時候，需要建立PrefixSum的表格，長度為Ｏ（ｎ）
O( 1 ) : sumRange(left, right)，直接查表，就可以得到區間和的答案。

Reference:

[1] Python/JS/Go/C++ by prefix sum. [ With explanation ] - Range Sum Query - Immutable - LeetCode