这个算法使用DP吗？

Question

所以我最近一直在学习动态规划 (DP)，当我遇到以下问题时，我决定使用 DP，但由于我是算法的初学者，我不确定这是否是 DP 的有效示例。

问题：

给定一个数组 nums。我们将数组的运行总和定义为 runningSum[i] = sum(nums[0]…nums[i])。返回 nums 的运行总和。

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

这是我的“DP”解决方案：

class Solution {
    public int[] runningSum(int[] nums) {
        int[] arr = new int[nums.length];
        
        int sum = 0;
        
        for(int i = 0; i < nums.length; i++){
            arr[i] = nums[i] + sum;
            sum += nums[i];
        }
        
        return arr;
    }
}

Answer 1

根据维基百科：

为了使动态规划适用，问题必须具有两个关键属性：最优子结构和重叠子问题。如果一个问题可以通过组合非重叠子问题的最优解来解决，则该策略被称为“分而治之”。这就是归并排序和快速排序不属于动态规划问题的原因。

在您的情况下，您正在实施以下策略：

  sum_all(array) = array[0] + sum_all(array[1..])

每一步只有一个子问题，这意味着子问题没有重叠。事实上，这是一种分而治之的退化形式。