[LeetCode]Minimum Area Rectangle

这道题很明显是DP的题目，我们用dp[i]表示s[0:i]中所有的distinct subsequence的话(包括empty string)，我们需要得出递归公式：

• 对于dp[i]来说，如果位于i处的s[i]之前都没有出现的话，很明显dp[i] = dp[i - 1] * 2，因为所有之前的distinct subsequence都可以append s[i]而生成新的没有重复的subsequence。
• 如果s[i]之前出现过，比如s[j] == s[i]，那么s[0:j - 1]的distinct subsequence和s[i]组成的subsequence就会产生重复，所以我们要减去dp[j - 1], dp[i] = 2 * dp[i - 1] - dp[j - 1]

我们根据上面的递归公式求即可，最后结果去掉empty string即可。时间空间复杂度都为O(N)，代码如下：