动态规划---范围累加和查询

今天药忘吃喽~ 2022-05-23 07:49 172阅读 0赞

1、题目

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

Example:

Given nums = [-2, 0, 3, -5, 2, -1]
    
    sumRange(0, 2) -> 1
    sumRange(2, 5) -> -1
    sumRange(0, 5) -> -3

2、解答：累加和，注意向量的作用域

3、代码

C++代码

class NumArray {
    public:
        vector<int> num;
        NumArray(vector<int> nums) {
            for(int i=1;i<nums.size();i++)
                nums[i] += nums[i-1];
            num = nums;
        }
       
        int sumRange(int i, int j) {
            if(i==0)
                return num[j];
            return num[j] - num[i-1];
        }
    
    };

python代码

class NumArray:
    
        def __init__(self, nums):
            """
            :type nums: List[int]
            """
            self.nums = nums
            
    
        def sumRange(self, i, j):
            """
            :type i: int
            :type j: int
            :rtype: int
            """
            return sum(self.nums[i:j+1])

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关贪心算法和动态规划

贪心算法（Greedy Algorithm）和动态规划（Dynamic Programming）都是解决优化问题的算法，但它们在问题求解方法和适用性上有很大的区别。贪心算法

「爱情、让人受尽委屈。」/ 2024年02月26日 05:39/ 0 赞/ 80 阅读

相关 494 目标和（动态规划）

1. 问题描述：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如

妖狐艹你老母/ 2023年01月24日 02:12/ 0 赞/ 43 阅读

相关动态规划和贪心算法

动态规划讲的很清楚的一篇博客： [http://blog.csdn.net/baidu\_28312631/article/details/47418773][http_bl

系统管理员/ 2022年09月30日 06:55/ 0 赞/ 182 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 240 阅读

相关动态规划——最大累加和

动态规划？ Time Limit: 1000MS Memory Limit: 65536KB Problem Description 动态规划作为《运筹学》的一个分支

一时失言乱红尘/ 2022年07月13日 15:27/ 0 赞/ 174 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 428 阅读

相关动态规划---范围累加和查询

1、题目 Given an integer array nums, find the sum of the elements between indices i and j

今天药忘吃喽~/ 2022年05月23日 07:49/ 0 赞/ 173 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 299 阅读

相关递归和动态规划

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 递归算法就是通过解决同一问题的一个或多个更小的实例来最终

冷不防/ 2022年01月16日 01:45/ 0 赞/ 279 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 473 阅读