更新於 2024/09/24閱讀時間約 6 分鐘

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

raw-image

題目敘述

在學習過比較基本的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] 從第0項~第i項的總和



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

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

PrefixSum[i]

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

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

= [ 從第0項~第(i-1)項的總和 ]+第i項

= 從第0項~第i項的總和


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

RangeSum(left, right) 區間[left, right]的元素總和

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

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

留意邊界索引的處理


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

PrefixSum 前綴和的初始條件就是第0項 = 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(n)
O( 1 ) : sumRange(left, right),直接查表,就可以得到區間和的答案。


Reference:

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

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.