C++ 303. Range Sum Query - Immutable(Leet Code)

Leet Code_303. Range Sum Query - Immutable

Dynamic Programming

 

https://leetcode.com/problems/range-sum-query-immutable/

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

Array중 범위 안의 합 구하기

​

방법

1. Array중 범위 안의 합 구하기

 

결과

Array중 범위 안의 합 구하기

 

통과한 코드

class NumArray {
public:
    NumArray(vector<int>& nums) {
        arr = nums;
    }
    
    int sumRange(int i, int j) {
        int res = 0;
        for(int s = i ; s <= j ; s++)
        {
            res += arr[s];
        }
        return res;
    }
    vector<int> arr;
};

이게왜 DP로 되어있을까

 

다른 사람 코드

vector<int> res = {0};
NumArray(vector<int>& nums) {
    for(int k=0; k < nums.size(); k++) {
        res.push_back(nums[k] + res.back());
    }
}

int sumRange(int i, int j) {
    return res[j + 1] - res[i];
}

속도가 더 빠르다.

가독성은 그닥..