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^4calls will be made tosumRange.
動態測試時，最多有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
