231123 刷题日报-动态规划

今天主要看了DP，前几天频繁遇到DP打击有点大。。

1. 0-1背包问题

要点：

a. 三部曲：

1. 状态和选择

        状态：物品序号、背包容量

        选择：放、不放

2. dp数组定义、base case

        dp[i][w] 对于前i个物品，当前背包容量是w，这种情况下最大价值是dp[i][w]

        比如dp[3][5] = 6，对于给定的一系列物品中，如果只前3个物品做选择，当背包容量是5时，最多可以装下的价值是6

3.根据【选择】，思考状态转移逻辑

        第i个物品装入背包

                dp[i][w] = dp[i-1][w-wt[i-1]] + value[i-1]

        第i个物品不装入背包

                dp[i][w] = dp[i-1][w]

        注：i表示第i个，所以value[i-1]表示第i个物品价值

2. 0-1背包问题变体: 子集划分

101 分割等和子集

要点：

a. 往01背包上靠：因为要一分为2，所以只考虑一半，另一半自然会满足。即把sum/2看作是背包容量

b. dp[i][sum/2] 表示在容量sum/2的背包下，是否恰好能装满，dp数组装的是 [是否] 不再是 [大小]，这也说明dp数组含义非常重要

c. base case要注意：dp[..][0] = true，表示在容量0时，已经装满了

3.回溯和动规谁是谁爹

102 目标和

要点：

1.这题我用回溯从n到-1写的有问题，答案从0到n没有问题，没明白为什么

2.消除重叠子问题：

如何发现重叠子问题？看状态是否可能重复，

备忘录 key处理技巧，拼接字符串一定要加个,

然后dp也是，这个base case好难想啊，是不是划分子集问题的dp[..][0]都是1/true?

我错写成dp[..][0] = 0了，实际dp[..][0] = 1，给的解释居然是 “因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。“

目标和这个题目，用dp写，细节实在太多了

int[]

求和 Arrays.stream(int[]).sum()

求最值 Arrays.stream(int[]).max().asInteger()