java - 动态规划——求公式

Question

我无能为力地试图解决这个问题:

Let arr be an array of integers of length n (indexed from 1 to n).

Let M[s][i] be a matrix containing boolean values of, if there exist a subset of first i numbers of the array arr (arr[1], arr[2], ..., arr[i], ..., arr[n]), of which the sum is exactly s.

Find the recursive formula for the value of M[s][i] based on M[?][j], where j < i and arr contains j. You can assume that 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] 仅当存在第一个的子集时才为 truei - 1 个元素，其子集完全等于 s - arr[i]。

这个问题通常被称为子集和问题。它已经有多个答案 here