动态规划（DP: Dynamic Programming）详解

LeetCode

题目一

有序号为1~n这n项工作，每项工作在Si时间开始，在Ti时间结束。对于每项工作都可以选择参加与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与不同工作的时间段不能重叠。目标是参与尽可能多的工作，问最多能参与多少项工作？

图？？

这个问题乍一看有点棘手，由于每项工作间有时间段的重叠问题，而导致可能选了某个工作后接下去的几个选不了了。所以并不是简单地从起始时间开始，每次在可选的工作中选最早遇上的会达到最优。

事实上，不从遍历时间，而从遍历工作的角度上会更容易想到，每项工作其实都只有选和不选的区别。这就是动态规划最主要的思想。

假设用OPT(i)来表示在这1~i个工作中最多能参与多少项。那么对于当前的第i个工作：

• 如果选。则有 OPT(i) = 1 + OPT(pre[i]) // pre[i]表示第i个工作之前，离它最近的可选工作的序号（可以直接预处理出来）。
• 如果不选。则 OPT(i) = OPT(i-1) // 简单地去掉这个第i项即可

然后在选与不选的两种情况中取最优。

int OPT(int i)
{
    if(i == 0) return 0;
    return max(OPT(i-1), 1+OPT(pre[i]));
}

但这里会有个问题，这个递归可能会反复的计算某个值（比如图中的OPT(5)），浪费了很多时间。这也就是重叠子问题（overlap sub-problem），解决方案是用数组存下每次计算的答案，下次如果再要计算时直接用先前保留好的值就行（称为记忆化搜索）。

图？？？

int OPT(int i)
{
    if(i == 0) return 0;
    if(dp[i] != 0) return dp[i];
    return dp[i] = max(OPT(i-1), 1+OPT(pre[i]));
}

由于明显可以看出来这是一个从前往后更新的状态，每个OPT[i]都取决于它之前的值，所以也可以直接用一个for遍历更新。

dp[0] = 0;
for(int i = 1; i <= n; i++)
    dp[i] = max(dp[i-1],1+dp[pre[i]);

其实这道题还可以用贪心的思路解决，正确的贪法是每次选取结束时间最早的工作。证明大概是，这个方案在选取了相同数量的更早开始的工作时，最终结束时间不会比其他方案的更晚，所以不存在选取更多工作的方案。（严格意义的证明需要归纳法和反证法）

但个人感觉贪心总是很玄学，能把动规想清楚就还是稳妥的动规吧。

题目二

给出一组正整数，问能不能取出任意个求和恰好为S。如果能的话返回Ture，不能返回False。

图？？

同样的从“取和不取”的角度来考虑。如果用OPT(i,S)来表示从1~i这前i个数中去凑S的话：

• 选第i个。OPT(i,S) = OPT(i-1,S-arr[i])
• 不选第i个。OPT(i,s) = OPT(i-1,S)

最终返回的是OPT(i-1,S-arr[i]) || OPT(i-1,S)

这里出口的判断值得注意：
如果S为0，说明已经凑好了不需要再取了，直接返回true。
如果S不为0且i为0，这时已经没有办法凑了，直接返回false。

并且还有一个难想到的点，如果arr[i]>S，那么只能走不选的分支。

bool OPT(int i, int S)
{
    if(S == 0) return true;
    if(i == 0) return false;
    if(arr[i] > S) return OPT(i-1,S);
    return OPT(i-1,S-arr[i]) || OPT(i-1,S);
}

同样的需要用记忆化搜索开个dp数组存一下提高效率。

或者这里用另一种方法，直接非递归的遍历更新。

for(int s = 0; s <= S; s++) dp[0][s] = false;
for(int i = 0; i <= n; i++) dp[i][0] = true;
for(int i = 1; i <= n; i++)
    for(int s = 1; s <= S; s++)
    {
        if(arr[i] > S) dp[i][s] = dp[i-1,S];
        else dp[i][s] = dp[i-1,S-arr[i]] || dp[i-1,S]
    }