题解 | #数位染色#

package main

import (
	"fmt"
	"strconv"
)

/**
本质上就是0-1背包问题，只不过需要传入一半的sum值，即可解决问题。

*/

func solution(arr []int) string {
	sum := 0
	for _, val := range arr {
		sum += val
	}
	if sum%2 != 0 {
		return "No"
	}
	half := sum / 2
	dp := make([][]int, len(arr)+1)
	for i := range dp {
		dp[i] = make([]int, half+1)
	}
	//dp
	for r := 1; r < len(dp); r++ {
		for c := 1; c < len(dp[0]); c++ {
			if arr[r-1] > c {
				dp[r][c] = dp[r-1][c]
			} else {
				dp[r][c] = max(dp[r-1][c], dp[r-1][c-arr[r-1]]+arr[r-1])
			}
		}
	}
	if dp[len(dp)-1][len(dp[0])-1] == half {
		return "Yes"
	}
	return "No"
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
*
输入：
1234567

输出：
Yes

说明：
将3、4、7染成红色即可，这样3+4+7=1+2+5+6
*/
func main() {
	var str string
	fmt.Scanln(&str)
	arr := make([]int, len(str))
	for i, _ := range str {
		ele, _ := strconv.Atoi(string(str[i]))
		arr[i] = ele
	}
	fmt.Println(solution(arr))
}