Динамическое программирование - найди формулу

Question

Я бездумно пытаюсь решить эту проблему:

Пусть arr будет массивом целых чисел длины n (проиндексирован от 1 до n).

Пусть M[s][i] - матрица, содержащая логические значения, если существует подмножество первых i чисел массива arr (arr [1], arr [2], ..., arr [i], ..., arr [n]), из которых сумма точно равна s.

Найти рекурсивную формулу для значения M[s][i] на основе M[?][j], где j arr содержит j. Вы можете предположить, что M[s][0] = 0.

Как бы я нашел эту формулу? Буду благодарен за любую помощь.

Answer 1

Простая формула повторения, основанная на вашем определении M[s][i], будет иметь вид:

M[s][i] = M[s][i-1] || M[s-arr[i]][i-1]

Пояснение

• Если arr[i] не включенов подмножестве M[s][i] равно true, если существует подмножество первых i-1 элементов, сумма которых точно равна s.
• Если arr[i] включено в подмножество,M[s][i] может быть true, только если существует подмножество первых i - 1 элементов, которое имеет подмножество, точно равное s - arr[i].

Эта проблема обычно называется Задача подмножества сумм .Здесь уже есть несколько ответов здесь