判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例：
示例 1:
s = "abc", t = "ahbgdc"返回 true.
示例 2:
s = "axc", t = "ahbgdc"
一般解法
这题虽然有动态规划的标签，但不用动态规划也可以很容易完成，时间复杂度为O(n)。只需要遍历一些长字符串，在遍历过程中判断遍历的元素和短字符串中的元素是否相同。
public boolean isSubsequence(String s, String t) {if(s.equals("")){return true;}int index=0;for(int i=0;i<t.length();i++){if(t.charAt(i)==s.charAt(index)){index++;}if(index==s.length()){return true;}}return false;}
动态规划
子序列系列的题目，动态规划是很好的解法。虽然这道题遍历一次就可以得出结果，但对于更高难度的题目，这种方法是完全行不通的，所以，我们依然有必要学会用动规解决这道题目。
思想：
1.这道题无非就是判断从字符串t中能否选出几个字符可以拼成字符串s，那么对于t字符串中的每一个字符都有选或者不选两种选择。这个便是递归的思想
2.而我们这里需要用dp数组记录计算过程，因此我们还需确定在计算过程中，不同的选择会导致那些状态。
2.从题目我们可以看出，dp数组应该有两个约束状态：
- 字符串t的长度
- 最多选出s.len个字符
- 当前已经从s中选出了几个字符
所以dp数组可以写成二维的形式：
dp[x][y]:
x代表已经从t中选择了几个字符，x<=s.len ,
y代表长字符串t从0~x位置的字符串，
状态转移方程：
if s.charAt(x)==t.charAt(y) dp[x][y]=dp[x-1][y-1]
else dp[x][y]=dp[x][y-1]
即：如果x和y位置的字符相同，那么x位置上的这个字符肯定是t的子字符串，这个时候，如果0-x-1位置上的字符串也是t的子字符串，那么0-x位置的字符串就是t的子字符串。
如果x和y位置的字符不相同，那么我们需要看s 字符串0~x的位置上的字符是不是t字符串0~y-1位置上字符串的子字符串
public static boolean isSubsequence(String s, String t) {int x = s.length();int y = t.length();boolean[][] dp = new boolean[x + 1][y + 1];for (int i = 0; i <= y; i++) {dp[0][i] = true;}for (int i = 1; i <= x; i++) {for (int j = 1; j <= y; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[x][y];}