如何将分区问题建模为动态规划问题？

Question

2)DP问题满足2个性质：

>

重叠子问题

最优子结构

但我看不出满足上述性质的问题。

输出：false

无法将数组分区为等和集。

Answer 1

该问题是NP完全的，但对于较小的约束条件，可以用动态规划方法求解。

重复关系如下：

f（索引,和）=f（索引,和+ARR[索引])或f（索引+1,和-ARR[索引])

if(index >= arraySize) {
    if ( sum == 0 ) 
        return true;
    else
       return false;

}