标签: Dynamic Programming

评分 0, 满分 5 星
0 票

动态规划,设计状态dp[i][0]和dp[i][1]分别表示到第i个house为止,不抢劫该house和抢劫该house能够获取的最大值,一直转移到最后,dp[num.size()-1][0]和dp[num.size()-1][1]比较大的就是答案。

评分 0, 满分 5 星
0 票

本来写的搜索,太过暴力了。正解是动态规划,用dp[i]表示从输入字符串的最右开始,到从左起的下标是i的位置结束,是否能够匹配。转移就很简单了,看程序就能明白。

评分 0, 满分 5 星
0 票

如果做过最大子段和,那么这里的最大子段积也就不难想到了。动态规划的思想,记录当前正的最大值,同时保留负值,因为负值可能在下次操作的时候将变为正并且取代正值。