FilesExpand file tree

 master

/

leetcode115.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

20 lines (15 loc) · 679 Bytes

 master

/

leetcode115.java

Top

File metadata and controls

• Code
• Blame

20 lines (15 loc) · 679 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

package leetcode.dp;

public class leetcode115 {

public int numDistinct(String s, String t) {

int [][] dp=new int[t.length()+1][s.length()+1];

for (int j = 0; j < s.length() + 1; j++) dp[0][j] = 1;

for (int i = 1; i <t.length() + 1 ; i++) {

for (int j = 1; j <s.length() + 1 ; j++) {

if (t.charAt(i-1)==s.charAt(j-1)){ //匹配时，用此匹配或者不用此匹配 两种情况均可以

dp[i][j]=dp[i-1][j-1]+dp[i][j-1]; //不匹配时,回退到 s 的前j-1 表示 t 的前i位

}else dp[i][j]=dp[i][j-1];

}

}

return dp[t.length()][s.length()];

}

}