leetcode 115. Distinct Subsequences如何改进我的方法
来源：9-1 什么是动态规划
站在巨人的肩膀上丶
2018-04-23
public int numDistinct(String S, String T) {
int[] memo = new int[S.length()+1];
for(int i = 0 ; i < memo.length ; i++)
memo[i] = 1;
int pre = 0;
for(int j = 0; j < T.length() ; j++)
{
for(int i = 1 ; i <= S.length() ; i++){
int cur = pre;
if(T.charAt(j) == S.charAt(i-1))
cur += memo[i-1];
memo[i-1] = pre;
pre = cur;
}
memo[S.length()] = pre;
pre = 0;
}
return memo[S.length()];
}
我的算法能做到以空间复杂度O(S的长度)解决这个问题，但提交后通不过OJ依然报出内存溢出，请问波波老师这道题还有更好的压缩空间复杂度的解决方法吗（在面试中做类似动态规划问题需要对问题的进行空间压缩吗）
2回答
-
我怀疑现在这个问题在Leetcode上对于Java的OJ有bug。我使用C++，开 O(T * S) 的内存都能通过，但是对于Java，开O(T)的内存，却MLE，实在是不对劲。
对于这个问题，空间可以压缩到O(T)的级别。由于根据题目的描述，应该在大多数情况下，T比S小，所以对于大多数测试用例，O(T)是比O(S)小的：）
至于具体逻辑，你的代码还有优化空间，可以参考我的Java代码：
这个空间优化过程的逻辑其实很像背包问题的优化：）
C++可以通过的代码如下链接。其中main.cpp的空间复杂度是 O(T * S)的，也可以通过。。。
https://github.com/liuyubobobo/Play-Leetcode/tree/master/0115-Distinct-Subsequences/cpp-0115
关于这个问题在Leetcode上的判题bug，我去给Leetcode写封邮件问一下：）
至于面试中遇到动态规划问题要不要对空间进行压缩。首先，一定要给出解答！哪怕不是最优的！然后一点一点优化。如果考官一直让你优化，你谈及到对空间的优化，肯定是好的；不过有的时候，考官考动态规划，让你说出转移方程就结束了：）
012018-04-23 -
liuyubobobo
2018-04-24
我刚刚收到了Leetcode的邮件，他们已经修复了这个bug：）我已经测试了，现在我的这些Solution都可以顺利通过了：）https://github.com/liuyubobobo/Play-Leetcode/tree/master/0115-Distinct-Subsequences/java-0115/src
如果你的算法逻辑没有问题，应该也不会MLE了：）
继续加油！
10
相似问题