专栏首页学习日记Golang. Leetcode 416. Partition Equal Subset Sum.go

Golang. Leetcode 416. Partition Equal Subset Sum.go

版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89143593

思路

dp dp[i]:是否可以得到和i dp[i+v]=true,如果dp[i]==true,如果可以得到i,那么加上v就得到了i+v,所以dp[i+v]=true dp[0] =true,得到和0是可以的 循环处理获得dp,期间要判断是否已经得到了结果

code

func canPartition(nums []int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%2 == 1 {
		return false
	}
	dp := make([]bool, sum+1)
	for k := range dp {
		dp[k] = false
	}
	dp[0] = true
	for _, v := range nums {
		//注意,这里是倒着循环,避免被覆盖
		for i := sum; i >= 0; i-- {
			if dp[i] {
				dp[i+v] = true
			}
		}
		if dp[sum/2] {
			return true
		}
	}
	return false
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang Leetcode 718. Maximum Length of Repeated Subarray.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • Golang Leetcode 926. Flip String to Monotone Increasing.go

    dp解法 状态方程: 如果最后一位是0: dp[i][0] = dp[i-1][0] dp[i][1] = min(dp[i-1][0], dp[i-1...

    anakinsun
  • Golang Leetcode 516. Longest Palindromic Subsequence.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89211057

    anakinsun
  • 不同的二叉搜索树

    对于二叉树问题的一般解决思路为将该树分为根结点,左子树,右子树,然后再对左右子树各个击破,最终将信息返回到根结点。

    你的益达
  • Golang Leetcode 718. Maximum Length of Repeated Subarray.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • HDU-4405-Aeroplane chess

    ACM模版 描述 ? 题解 概率 DPDP,求期望。 状态转移方程很容易想,设 dp[i]dp[i] 表示在位置 ii 还需要多少期望才能到达终点,那么 dp[...

    f_zyj
  • HOJ 2124 &POJ 2663Tri Tiling(动态规划)

    Tri Tiling Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9...

    ShenduCC
  • 【leetcode刷题】T167-整数拆分

    https://leetcode-cn.com/problems/integer-break/

    木又AI帮
  • 【USACO 3.2】Stringsobits (dp)

    状态转移:dp[i][j]=dp[i-1][j]+dp[i-1][j-1],即第i位放1或者0。

    饶文津

扫码关注云+社区

领取腾讯云代金券