3180. 执行操作可获得的最大总奖励 I

力扣刷题记录

dp 回溯

3180. 执行操作可获得的最大总奖励 I

思路

和往常一样，先使用暴力求解，想到了回溯算法，选择了当前数字，就跳到下一个数字，形成一个树形结构来遍历所有结果集合，但是没有找到优化算法，时间复杂度比较高

但是也可以通过90%的测试用例

没办法，只能思考动态规划的问题，没有想出来，查看题解
首先对数组进行排序
定义动态数组 dp[2 * max] , max表示最大的奖励数字
dp数组记录值为0或1，表示该下标的值是否能够被取到

最大的奖励数不可能超过2 * max，因此遍历奖励数组，当前值为x时，倒序k遍历 2 * x - 1到x，判断dp[k - x]是否可以取到，如果可以取到，那么dp[k]也可以达到，标记为1

最后遍历dp数组找到最大值即可

代码

var res int = 0func backTracking(rewardValues []int, curReward int, pos int){if curReward > res{res = curReward}if pos >= len(rewardValues){return}for i := pos; i < len(rewardValues); i++{if curReward < rewardValues[i]{curReward += rewardValues[i]backTracking(rewardValues, curReward, i + 1)curReward -= rewardValues[i]}}
}func maxTotalReward(rewardValues []int) int {sort.Ints(rewardValues)// res = 0// backTracking(rewardValues, 0, 0)max := rewardValues[len(rewardValues) - 1]dp := make([]int, 2 * max)dp[0] = 1for _, x := range rewardValues{for k := 2 * x - 1 ; k >= x ; k --{// k 表示能到达的最大总奖励if dp[k-x] == 1{dp[k] = 1}}}for i, val := range dp{if val == 1{res = i}}return res
}

不考虑排序算法的情况下
时间复杂度：O(n*max)
空间复杂度：O(max)