Readme

1349.Maximum-Students-Taking-Exam

本题如果用DFS来做的话会TLE。如果充分利用row的状态来做DP的话，可以节省很多不必要的重复搜索。举个例子来说，第四排如何安排，完全仅仅取决于第三排是怎么安排的，第一和第二排对其而言并没有直接的影响。如果你是搜索算法的话，可能发现有非常多第一和第二排的不同策略，但是对应的第三排的策略可以是相同的。这样的话，如果强制走遍每一种“row1-row2-row3-row4”的组合才能确定row4的计数的话，就很不经济。

所以我们设计dp[i][s]表示将第i行安排成状态s时，前i行最多能安排多少人。s是一个8bit的整型数字就足以代表每一个行的策略（每个bit表示该位置是否坐人），范围就是[0,255]。对于dp[i][s]，我们只需要遍历所有的dp[i-1][t]（表示第i-1行安排成状态t的策略），查看s本身是否合法，以及策略s能否接在策略t后面。都满足的话，那么dp[i][s]及可以更新为dp[i-1][t]+count(s)，其中count(s)表示第i行安排策略s所对应的该行的人数。

输出的答案是你在生成所有dp[i][s]过程中最大的那个。注意，不一定是dp[M-1][s]中最大的那个。

Leetcode Link