|
| 1 | +##Guessing |
| 2 | + |
| 3 | +Lets start with`rabbbit` and`rabbit`. |
| 4 | + |
| 5 | +To make the problem easier, start from one char,`distinct subsequences` of`rabbbit` and`r`. |
| 6 | + |
| 7 | +`distinct subsequences` below, by eyeball: |
| 8 | + |
| 9 | +*`r` and`r` has 1`distinct subsequences` |
| 10 | +*`a` and`r` has 0`distinct subsequences` |
| 11 | + |
| 12 | +These two are easy to be understood. |
| 13 | + |
| 14 | +*`ra` and`r` has 1`distinct subsequences` |
| 15 | +*`rab` and`r` has 1`distinct subsequences` |
| 16 | +*`rabbbbbbbbbbbb` and`r` has 1`distinct subsequences` |
| 17 | + |
| 18 | +These three show that`r` plus any junk chars will not change`distinct subsequences` |
| 19 | + |
| 20 | +*`rr` and`r` has 2`distinct subsequences` |
| 21 | +*`rar` and`r` has 2`distinct subsequences` |
| 22 | +*`rara` and`r` has 2`distinct subsequences` |
| 23 | +*`rarar` and`r` has 3`distinct subsequences` |
| 24 | + |
| 25 | +`rar` and`r` is same as`rr` and`r`, because`a` there has nothing to do with the number of`distinct subsequences`, it is a junk like above. |
| 26 | + |
| 27 | +In another word,`rar` and`r` can be converted to`ra` +`r` and`r`, that is`1 + 1`. |
| 28 | + |
| 29 | +###Put them into table |
| 30 | + |
| 31 | +the value`P[i][j]` means that`S[0..i]` and`T[0..j]` has`P[i][j]``distinct subsequences`. |
| 32 | + |
| 33 | +the table with only one char |
| 34 | + |
| 35 | +``` |
| 36 | ++---+---+---+---+---+---+---+---+ |
| 37 | +| | r | a | b | b | b | i | t | |
| 38 | ++---+---+---+---+---+---+---+---+ |
| 39 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 40 | ++---+---+---+---+---+---+---+---+ |
| 41 | +``` |
| 42 | + |
| 43 | +Enlarge the table |
| 44 | + |
| 45 | + |
| 46 | +``` |
| 47 | ++---+---+---+---+---+---+---+---+ |
| 48 | +| | r | a | b | b | b | i | t | |
| 49 | ++---+---+---+---+---+---+---+---+ |
| 50 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 51 | ++---+---+---+---+---+---+---+---+ |
| 52 | +| a | | | | | | | | |
| 53 | ++---+---+---+---+---+---+---+---+ |
| 54 | +| b | | | | | | | | |
| 55 | ++---+---+---+---+---+---+---+---+ |
| 56 | +| b | | | | | | | | |
| 57 | ++---+---+---+---+---+---+---+---+ |
| 58 | +| i | | | | | | | | |
| 59 | ++---+---+---+---+---+---+---+---+ |
| 60 | +| t | | | | | | | | |
| 61 | ++---+---+---+---+---+---+---+---+ |
| 62 | +``` |
| 63 | + |
| 64 | +Some grids here are easy to be filled, the grids which`j > i`. |
| 65 | +That is, T is longer than S, there will be no`distinct subsequences`. |
| 66 | + |
| 67 | +``` |
| 68 | ++---+---+---+---+---+---+---+---+ |
| 69 | +| | r | a | b | b | b | i | t | |
| 70 | ++---+---+---+---+---+---+---+---+ |
| 71 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 72 | ++---+---+---+---+---+---+---+---+ |
| 73 | +| a | 0 | | | | | | | |
| 74 | ++---+---+---+---+---+---+---+---+ |
| 75 | +| b | 0 | 0 | | | | | | |
| 76 | ++---+---+---+---+---+---+---+---+ |
| 77 | +| b | 0 | 0 | 0 | | | | | |
| 78 | ++---+---+---+---+---+---+---+---+ |
| 79 | +| i | 0 | 0 | 0 | 0 | | | | |
| 80 | ++---+---+---+---+---+---+---+---+ |
| 81 | +| t | 0 | 0 | 0 | 0 | 0 | | | |
| 82 | ++---+---+---+---+---+---+---+---+ |
| 83 | +``` |
| 84 | + |
| 85 | +`j == i` grids are easy too, the S and T must be the same if it wants to have 1`distinct subsequences`. |
| 86 | + |
| 87 | +``` |
| 88 | ++---+---+---+---+---+---+---+---+ |
| 89 | +| | r | a | b | b | b | i | t | |
| 90 | ++---+---+---+---+---+---+---+---+ |
| 91 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 92 | ++---+---+---+---+---+---+---+---+ |
| 93 | +| a | 0 | 1 | | | | | | |
| 94 | ++---+---+---+---+---+---+---+---+ |
| 95 | +| b | 0 | 0 | 1 | | | | | |
| 96 | ++---+---+---+---+---+---+---+---+ |
| 97 | +| b | 0 | 0 | 0 | 1 | | | | |
| 98 | ++---+---+---+---+---+---+---+---+ |
| 99 | +| i | 0 | 0 | 0 | 0 | 0 | | | |
| 100 | ++---+---+---+---+---+---+---+---+ |
| 101 | +| t | 0 | 0 | 0 | 0 | 0 | 0 | | |
| 102 | ++---+---+---+---+---+---+---+---+ |
| 103 | +``` |
| 104 | + |
| 105 | +This pictrue is just encouraging you, as there is only a few grids left to be filled. |
| 106 | + |
| 107 | +###`rab` and`ra` |
| 108 | + |
| 109 | +This problem looks familiar. It is the`ra` and`r`. |
| 110 | + |
| 111 | +as`b` is a junk char,`rab` should have the same number as`ra` and`ra`. |
| 112 | + |
| 113 | +Then the table is like |
| 114 | + |
| 115 | +``` |
| 116 | ++---+---+---+---+---+---+---+---+ |
| 117 | +| | r | a | b | b | b | i | t | |
| 118 | ++---+---+---+---+---+---+---+---+ |
| 119 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 120 | ++---+---+---+---+---+---+---+---+ |
| 121 | +| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 122 | ++---+---+---+---+---+---+---+---+ |
| 123 | +| b | 0 | 0 | 1 | | | | | |
| 124 | ++---+---+---+---+---+---+---+---+ |
| 125 | +| b | 0 | 0 | 0 | 1 | | | | |
| 126 | ++---+---+---+---+---+---+---+---+ |
| 127 | +| i | 0 | 0 | 0 | 0 | 0 | | | |
| 128 | ++---+---+---+---+---+---+---+---+ |
| 129 | +| t | 0 | 0 | 0 | 0 | 0 | 0 | | |
| 130 | ++---+---+---+---+---+---+---+---+ |
| 131 | +``` |
| 132 | + |
| 133 | +###`rabb` and`rab` |
| 134 | + |
| 135 | +This time, add a new`b` to both`rab` and`ra`. |
| 136 | + |
| 137 | +####Use the new`b` in subsequences |
| 138 | + |
| 139 | +This time they have same letter,`b` , at the end. It is not a junk. |
| 140 | + |
| 141 | +This time, remove`b` from both S and T, then they become`rab` and`ra`. |
| 142 | + |
| 143 | +that is, this will take`rab` and`ra``distinct subsequences`. |
| 144 | + |
| 145 | +####Dont use the new`b` |
| 146 | + |
| 147 | +Treat`b` as junk, it has`rab` and`rab``distinct subsequences`. |
| 148 | + |
| 149 | + |
| 150 | +####Sum up two choices |
| 151 | + |
| 152 | +Use or not will result two set of`distinct subsequences`, so sum them up. |
| 153 | + |
| 154 | +`rabb` and`rab` =`rab` and`ra` +`rab` and`rab`. |
| 155 | + |
| 156 | +``` |
| 157 | ++---+---+---+---+---+---+---+---+ |
| 158 | +| | r | a | b | b | b | i | t | |
| 159 | ++---+---+---+---+---+---+---+---+ |
| 160 | +| r | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 161 | ++---+---+---+---+---+---+---+---+ |
| 162 | +| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 163 | ++---+---+---+---+---+---+---+---+ |
| 164 | +| b | 0 | 0 | 1 | 2 | | | | |
| 165 | ++---+---+---+---+---+---+---+---+ |
| 166 | +| b | 0 | 0 | 0 | 1 | | | | |
| 167 | ++---+---+---+---+---+---+---+---+ |
| 168 | +| i | 0 | 0 | 0 | 0 | 0 | | | |
| 169 | ++---+---+---+---+---+---+---+---+ |
| 170 | +| t | 0 | 0 | 0 | 0 | 0 | 0 | | |
| 171 | ++---+---+---+---+---+---+---+---+ |
| 172 | +``` |
| 173 | + |
| 174 | +##General form |
| 175 | + |
| 176 | +the grid`P[i][j]` has 1 choice when`S[i] != T[j]`, this only adds some junk chars. |
| 177 | + |
| 178 | +``` |
| 179 | +P[i][j] = P[i - 1][j] |
| 180 | +``` |
| 181 | + |
| 182 | +the grid`P[i][j]` has 2 choice when`S[i] == T[j]` |
| 183 | + |
| 184 | +``` |
| 185 | +P[i][j] = |
| 186 | +P[i - 1][j] // adds as junk chars. |
| 187 | ++ |
| 188 | +P[i - 1][j - 1] // use the new char in the new subsequence |
| 189 | +
|
| 190 | +``` |
| 191 | + |
| 192 | +Fill up the table and the bottom right grid is the answer. |
1 | 193 |
|
2 | | -##TODO |
3 | | -* write down thinking |
4 | 194 |
|