leetCode 303. Range Sum Query - Immutable | Dynamic Programming

303. Range Sum Query - Immutable 

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Note:

You may assume that the array does not change.

There are many calls to sumRange function.

題目大意：求數組一個連續子集的和。

思路：

1.可以直接找到數組子集的起始位置，連續相加到終止位置，

就可以得到答案。這樣的話，沒計算一次都要連續相加，比較麻煩。是以想到下面的思路。

2.用一個數組來存放目前元素的之前元素的和。

例如：

vector<int> source,源數組

vector<int> preITotal,用來存放source前i個元素的和，包括第i個元素。

以後每次計算範圍源數組[i,j]範圍子集的和，preITotal[j] - preITotal[i-1].計算即可。

代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

<code>class</code> <code>NumArray {</code>

<code>private</code><code>:</code>

<code>    </code><code>vector&lt;</code><code>int</code><code>&gt; preITotal;</code><code>//存放前i個元素的和</code>

<code>public</code><code>:</code>

<code>    </code><code>NumArray(vector&lt;</code><code>int</code><code>&gt; &amp;nums) {</code>

<code>        </code><code>if</code><code>(nums.empty())</code>

<code>            </code><code>return</code><code>;</code>

<code>        </code><code>preITotal.push_back(nums[0]);</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 1; i &lt; nums.size(); ++i)</code>

<code>            </code><code>preITotal.push_back(preITotal[i-1] + nums[i]);</code>

<code>    </code><code>}</code>

<code>    </code><code>int</code> <code>sumRange(</code><code>int</code> <code>i, </code><code>int</code> <code>j) {</code>

<code>        </code><code>if</code><code>(0 == i)</code>

<code>            </code><code>return</code> <code>preITotal[j];</code>

<code>        </code><code>return</code> <code>preITotal[j] - preITotal[i - 1];</code>

<code>};</code>

<code>// Your NumArray object will be instantiated and called as such:</code>

<code>// NumArray numArray(nums);</code>

<code>// numArray.sumRange(0, 1);</code>

<code>// numArray.sumRange(1, 2);</code>

總結：

題目标注為動态規劃，開始怎麼也想不出哪裡用到動态規劃的思想了。當把目前的結果記錄下來，以後使用這一點，和動态規劃挂鈎了。

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1844975