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

Question

我无法理解如何将这个分区问题看作是一个动态规划问题。

我有以下疑问：

( 1)这不是一个优化问题(或者我看不见)，那么为什么我们要应用DP方法呢？

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

1. 重叠子问题
2. 最优子结构 但我看不出满足上述性质的问题。

划分问题是确定给定集合是否可以划分成两个子集，以便两个子集中的元素之和是相同的。

arr[] = {1，5，11，5}

输出:真

数组可以划分为{1、5、5}和{11}

arr[] = {1，5，3}

输出:假

不能将数组划分为等和集。

Answer 1

这个问题是NP-完全的，但是对于较小的约束，它是可以用动态规划来解决的。

复发关系如下：

f(index，sum) = f(index，sum + arrindex)或f(index+1，sum - arrindex)

至于基本情况：

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

}

该函数的时间复杂度和内存复杂度将导致O( arraySize * maximumSum)。因此，如果arraySize * maximumSum足够小，则使用动态规划可以解决这个问题。