题目描述
给你一个数组 nums 。数组「动态和」的计算公式为：
runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
示例 1：
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：
输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：
输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/running-sum-of-1d-array
解题思路一
这道题本身思路很简单，首先如果仅考虑到时间复杂度的问题，那么用一个标记tempSum来记录每次循环时的累加值，并将该累加值存入新数组中，循环结束后将新数组返回。其代码如下：
public int[] runningSum(int[] nums) {
//暂存的累加值变量
int currentSum = 0;
//返回的数组，数组长度与传入的数组长度相等
int[] resultArrary = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
currentSum += nums[i];
resultArrary[i] = currentSum;
}
return resultArrary;
}
提交到LeetCode之后，其运行结果如下：
那么有没有方法不额外声明变量就能获得结果呢？
解题思路二
可以改变数组中每个元素的值，在循环时下一个数组元素的值：
array[i+1] += array[i]
这样依次累加，循环结束后该数组即为所需结果。其代码如下：
public int[] runningSum(int[] sums) {
for (int i = 0; i < sums.length - 1; i++) {
sums[i + 1] += sums[i];
}
return sums;
}
提交到LeetCode之后，其运行结果如下：
内存消耗比方法一要小。
在面试时要注意问清面试官是否可以修改传入的数组，从而针对应答。
算法原理
这里的两种解题思路与动态规划算法类似，下面简单介绍一下动态规划算法：
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
其他LeetCode中动态规划相关问题：
39. 组合总和
LCP 12. 小张刷题计划
LCP 16. 游乐园的游览计划
1235. 规划兼职工作
1466. 重新规划路线
剑指 Offer 13. 机器人的运动范围
剑指 Offer 59 - I. 滑动窗口的最大值
