动态规划---判断子序列

题目：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

思路：本题与最长公共子序列思路基本一致，只是在处理两字符串字符不一致时有点改变

1.确定dp数组及含义

dp[i][j]代表[0,i-1]长度的字符串s,[0.j-1]长度的字符串t的最长公共子序列

2.确定递推公式

如果s[i-1]=t[j-1]，那么找到了一个公共元素，dp[i][j]=dp[i-1][j-1]+1

如果s[i-1]！=t[j-1]，那么将t回退（这就是两题的不同之处），dp[i][j]=dp[i][j-1]

3.初始胡dp数组

所有元素初始化为0

4.确定遍历顺序

外层for循环遍历字符串s，内层for循环遍历字符串t，从小到大遍历

代码：

    public boolean isSubsequence(String s, String t) {int len1=s.length();int len2=t.length();int[][] dp=new int[len1+1][len2+1];for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=dp[i][j-1];}}}if(dp[len1][len2]==len1)return true;elsereturn false;}