Использует ли этот алгоритм DP?

Question

Итак, я недавно изучал Dynami c Programming (DP), и когда я столкнулся со следующей проблемой, я решил использовать DP, но, поскольку я новичок в алгоритмах, я не уверен, что это действительный пример DP или нет.

Проблема:

Учитывая массив nums. Мы определяем текущую сумму массива как runningSum [i] = sum (nums [0]… nums [i]). Вернуть текущую сумму чисел.

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

Согласно Википедии :

Есть два ключевых атрибута, которые проблема должна иметь для применения динамического c программирования: оптимальная субструктура и перекрывающиеся субструктуры. проблемы. Если проблема может быть решена путем комбинирования оптимальных решений неперекрывающихся подзадач, стратегия называется «разделяй и властвуй» . Вот почему сортировка слиянием и быстрая сортировка не классифицируются как проблемы динамического c программирования.

В вашем случае вы реализуете следующую стратегию:

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

На каждом шаге есть только одна подзадача, и это означает, что подзадачи нет перекрытия. В самом деле, это выродившаяся форма «разделяй и властвуй».

Answer 2

Думаю, главное, почему я не решаюсь называть ваш алгоритм DP, - это отсутствие оптимизации. Конечно, ваша задача может быть разделена на более мелкие подзадачи и результат для размера n складывается из результата для размера n-1. Но DP - это стратегия оптимизации. Я не вижу ничего, что можно было бы оптимизировать в вашей задаче.

Answer 3

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

Просто используйте это:

Создайте массив префиксов, и каждый элемент этого массива является суммой предыдущего элемента и элемента исходного массива

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];
}