Is this algorithm using DP?

user_12126360 0
Viewed 130

So I have been learning Dynamic Programming (DP) recently and when I came upon the following problem, I decided to use DP but since I'm a beginner in algorithms, I am not sure if this is a valid example of DP or not.

Problem:

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of 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].

This is my "DP" solution:

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;
    }
}
dynamic-programming java
4 Answers

According to Wikipedia:

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems.

In your case, you are implementing following strategy:

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

At each step there is only one subproblem, and that means there is no overlap of the subproblems. Indeed, this is a degenerate form of divide and conquer.

user_1399850

I think the main thing why I'm hesitant to call your algorithm DP is absence of optimization. Certainly, your task can be divided to smaller subtasks and result for size n assembled from result for size n-1. But DP is optimization strategy. I cannot see anything to be optimized in your task.

user_6535390 
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].

Just use this:

Create a prefix array and every element of this array is the sum of previous element and element of original array

int[] P = new int[4];
for (int i = 0; i < 4; i++)
{
  if (i == 0) P[i] = nums[i];
  else P[i] = P[i-1] + nums[i];
}
user_138692330

Also this is good to use

vector<int> P; // running sum list
vector<int> nums = {1,2,3,4}; // given input
int sum = 0; // sum at any running position
for(auto x : nums) 
{
   P.push_back(sum+x);
   sum += x;
}
user_158854620
Related