My code:
public class Solution {
public int numDistinct(String s, String t) {
if (s == null || t == null) {
return 0;
}
else if (s.length() == 0) {
return 0;
}
else if (t.length() == 0) {
return s.length();
}
int m = s.length();
int n = t.length();
int[][] dp = new int[m][n];
int counter = 0;
char target = t.charAt(0);
for (int i = 0; i < m; i++) {
char curr = s.charAt(i);
if (curr == target) {
counter++;
}
dp[i][0] = counter;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j];
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
真的没想到这道题目我可以自己做出来。。。还是很兴奋的。
iteration DP
dp[i][j] 表示， s[0, i] 与 t[0, j] 的 distinct subsequences
那么递推式是什么呢？
假设给了我们这两个string
s[0, i] 与 t[0, j]
那么，
dp[i][j] = dp[i - 1][j];
if (t[j] == s[i]) {
dp[i][j] += dp[i - 1][j - 1];
}
即， dp[i][j] 至少等于 dp[i - 1][j]
如果 s[i] == t[j]
那么，还要看 s[0, i - 1] 与 t[0, j - 1] 的匹配状态，
即， dp[i][j] += dp[i - 1][j - 1]
这么一看，思路好像很简单。
这就是DP吧。其实我一开始思路也没有直接就这么简洁。
提交了几次，失败后，再看代码逻辑，逐渐改出来的。
初始状态是什么？
dp[i][0], 看 s[0, i] 里面有多少个字母 == t[0]
dp[0][j] = 0, j > 0
差不多就这样了吧。
然后我发现DP做到现在大致分为四类题目。
第一种的典型题目是
burst ballon
给你一个数组，你需要 divide and conquer, 将数组整体劈成两个独立的个体，分别计算，再统计结果。中间加上cache以加快速度。
from top to bottom
也可以用iteration DP来做，但很难想到。
edit distance
两个string，完全可以用 dp[][] 来解决。这道题目也是这个类型。
不是劈开。而是从无到有，从底到顶
from bottom to top
house robbing, best time to buy and sell stock with cooldown
状态机, state machine. 画出 状态机，然后照着写出dp递归式，就差不多了。
perfect square, climbing stair, Integer Break
这些都是生成一个数组， nums[n]
然后， nums[i] 与 nums[0, i - 1] 有关。
比如， perfect square, nums[i] 可能 =
nums[1] + nums[i - 1]
nums[2] + nums[i - 2]
nums[3] + nums[i - 3]
...
然后采用某种策略，省去一些多余的例子。
Integer break 也是如此。
这只是我的一种感觉，理论上肯定有很多不足。但对解决DP题目还是会有一定帮助的。就像看到时间要求如果有含 log n 项， 那么，就一定存在 binary search 这样的东西。
Anyway, Good luck, Richardo! -- 08/27/2016
