Articles under the label of 动态规划

打家劫舍定义 dp[i] 为前 i 个房子抢到的最大金额，那么有 $dp[i] = max(dp[i-1], dp[i-2] + nums[i])$func rob(nums []int) int { n := len(nums) if n == 1 { return nums[0] } dp := make([]int, n) dp[...

这道题要分割出两个数组，平均值需要相等，那其实就相当于分出一个有k个元素的数组的平均值和整体数组的平均值相等就可以满足了，也就是 $target / k = sum / n$。那么 $target = sum * k / n$所以我们需要求的其实就是不同的 k 对应的和（target）是否等于 sum * k / n所以定义可达性 DP 数组如下：dpk 代表刚好 k 个数能组成的和有哪些，...

看到这道题的第一印像是用dp，$dp[i][j]$ 代表 $s[i..j]$ 的回文子串最大长度，后来发现这个定义好像做不出来。遂看答案，结果发现定义应该是代表 $s[i..j]$ 是否为回文串。然后就是需要看如何通过现有状态得到后面的状态，首先考虑回文串如何判断，如果有 $s[i] == s[j]$，且 $j-i <= 2$ 则必为 true，如果 $dp[i+1][j-1]$ 为 ...