416分割等和子集.md

一维dp数组：

func canPartition(nums []int) bool {
    var sum int
    for _, n := range nums {
        sum += n
    }
    if sum % 2 == 1 {
        return false
    }
    sum /= 2
    // dp[j]为在容量为j的背包中能放的数值的最大和
    dp := make([]int, sum+1)
    for i := 0; i < len(nums); i++ {
        // j >= nums[i]是因为当nums[i]超过了j时，无法放入背包，不用考虑，保持原有值即可
        for j := sum; j >= nums[i]; j-- { 
            // 比较两种情况：不放入i和放入i
            dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
        }
    }
    return dp[sum] == sum
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

二维dp数组：

func canPartition(nums []int) bool {
    var sum int
    for _, n := range nums {
        sum += n
    }
    if sum % 2 == 1 {
        return false
    }
    sum /= 2
    // dp[i][j]为从下标0-i的数中任意选择放入容量为j的背包中能放的数值的最大和
    dp := make([][]int, len(nums))
    for i := range dp {
        dp[i] = make([]int, sum+1)
    }
    // 初始化
    // dp[i][0] 背包容量为0时全部为0
    // dp[0][j] 当背包容量大于第0个数时，最大值为nums[0]
    for j := nums[0]; j <= sum; j++ {
        dp[0][j] = nums[0]
    }
    for i := 1; i < len(nums); i++ { // 从1开始遍历数组
        for j := 0; j <= sum; j++ {
            if j < nums[i] { // 当容量小于当前数，无法放入
                dp[i][j] = dp[i-1][j] 
            } else { // 可以放入，比较放入和不放入那个总价值更大
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])
            }
        }
    }
    return dp[len(nums)-1][sum] == sum
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}