题目关键信息：
给定一个数组，将数组分成两个部分，使得这两部分的和的差最小

方法一：动态规划
“数组”，“求最优值”显然这道题可以用动态规划解决，这是0-1背包的变形类题目，求数组两部分的和的差的最小值，假设数组的总和为，部分一的和为，部分二的和为，那么增加，就减小,减小,就增加,,因此背包的最大容量是,只有当不断接近时，他们的差才会最小，于是，我们将问题转化为，在的背包容量中，怎样放置物品才能使尽可能地填满背包。
明确了可选物品的数量是数组的大小，背包的最大容量是后，我们定义数组，明确数组的含义，的含义就是背包容量是j的情况是背包内所装的前个物品的最大价值。

  • :背包容量装不下第个礼物，不装下，继承的值
  • 背包容量装得下第个物品,在装下与不装下中选择最大值,即

图片说明

Java版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型一维数组 每个礼物的价值
     * @return int整型
     */
    public int maxPresent (int[] presentVec) {
        // write code here
        int sum=0;
        for(int i=0;i<presentVec.length;i++){
            sum+=presentVec[i];
        }
        //背包总容量为sum/2
        int m=presentVec.length,n=sum/2;
        //dp[i][j]表示在背包容量为j的情况下，背包里前i个物品所具有的最大价值
        int[][]dp=new int[m+1][n+1];
        //遍历背包中的物品
        for(int i=1;i<=m;i++){
            //遍历背包的容量
            for(int j=1;j<=n;j++){
                //第i件物品的容量大于背包容量
                if(presentVec[i-1]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                 //在装入与不装入之间取最大值
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-presentVec[i-1]]+presentVec[i-1]);
                }
            }
        }
        return Math.abs(sum-2*dp[m][n]);
    }
}

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型vector 每个礼物的价值
     * @return int整型
     */
    int maxPresent(vector<int>& presentVec) {
        // write code here
        int sum=0;
        for(int i=0;i<presentVec.size();i++){
            sum+=presentVec[i];
        }
        //背包总容量为sum/2
        int m=presentVec.size(),n=sum/2;
        //dp[i][j]表示在背包容量为j的情况下，背包里前i个物品所具有的最大价值
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        //遍历背包中的物品
        for(int i=1;i<=m;i++){
            //遍历背包的容量
            for(int j=1;j<=n;j++){
                //第i件物品的容量大于背包容量
                if(presentVec[i-1]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                 //在装入与不装入之间取最大值
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-presentVec[i-1]]+presentVec[i-1]);
                }
            }
        }
        return abs(sum-2*dp[m][n]);
    }
};

复杂度：
时间复杂度：外层循环次，内层循环次，时间复杂度为
空间复杂度:额外创建的数组大小为,复杂度为

优化后的动态规划
的状态只和的状态有关,我们可以采用滚动数组，将二维数组压缩为一维，具体做法是只保留j这个维度，每一次在遍历第i个物品时,保存着遍历完前i个物品后背包的价值，即还没被新结果覆盖时相当于相当于二维数组中的,为什么这里的j要从后往前遍历呢？因为如果j从前往后遍历，当i不变时，前面已经计算过的会覆盖后面的的意义不等于二维数组中的

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVec int整型一维数组 每个礼物的价值
     * @return int整型
     */
    public int maxPresent (int[] presentVec) {
        // write code here
        int sum=0;
        for(int i=0;i<presentVec.length;i++){
            sum+=presentVec[i];
        }
        //背包总容量为sum/2
        int m=presentVec.length,n=sum/2;
        //dp[i][j]表示在背包容量为j的情况下，背包里前i个物品所具有的最大价值
        int[]dp=new int[n+1];
        //遍历背包中的物品
        for(int i=1;i<=m;i++){
//j要从后往前遍历，否则当i不变时，前面已经计算过的dp[j-presentVec[i-1]]会覆盖后面的dp[j-presentVec[i-1]]
//dp[j-presentVec[i-1]]的意义不等于二维数组中的dp[i-1][j-presentVec[i-1]],边界条件是背包容量要装得下第i个物品
//遍历第i个物品时,dp[j]保存着遍历完前i个物品后背包的价值，即dp[j]还没被新结果覆盖时相当于dp[i-1][j]
            for(int j=n;j>=presentVec[i-1];j--){
                    dp[j]=Math.max(dp[j],dp[j-presentVec[i-1]]+presentVec[i-1]);
                }
        }
        return Math.abs(sum-2*dp[n]);
    }
}

复杂度：
时间复杂度：外层循环次，内层循环次，时间复杂度为
空间复杂度：额外创建的数组大小为,复杂度为