Сообщите обо всех длинных общих подпоследовательностях (LCS) и их адаптивном расположении в двух строках
Я только что закончил программу, которая позволяет сообщать обо всех возможных LCS и местоположении двух строк соответственно. Тем не менее, результат теста не совсем правильно.
Например, если две строки - "AACADBCDADCB" и "DCACDCBBDBAD", правильный результат должен содержать 8 случаев. Мой вывод просто сообщить о 6 случаях, как показано ниже:
--- Выход --- Макс. длина = 7
LCS: ACDBDAD, в X: 2 3 5 6 8 9 10, в Y: 3 4 5 7 9 11 12
LCS: ACDBDAD, в X: 2 3 5 6 8 9 10, в Y: 3 4 5 8 9 11 12
LCS: ACDCDAD, в X: 2 3 5 7 8 9 10, в Y: 3 4 5 6 9 11 12
LCS: CADBDAD, в X: 3 4 5 6 8 9 10, в Y: 2 3 5 7 9 11 12
LCS: CADBDAD, в X: 3 4 5 6 8 9 10, в Y: 2 3 5 8 9 11 12
LCS: CADCDAD, в X: 3 4 5 7 8 9 10, в Y: 2 3 5 6 9 11 12
Пожалуйста, дайте мне несколько предложений. Довольно Спасибо!
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
public class LCSMain {
//test case
private static String x = "AACADBCDADCB";
private static String y = "DCACDCBBDBAD";
private static int maxLength = 0;
private static List<String> maxNodelist = new ArrayList<String>();
private static int[][] len = null;
private static int[][] type = null;
private static TreeSet<String> outputSet = new TreeSet<String>();
public static void main (String[] args) {
len = new int[x.length()+1][y.length()+1];
type = new int[x.length()+1][y.length()+1];
dpMatrix(x,y);
//Backtrack all possible LCS and add the results into outputSet
for(int count=0; count< maxNodelist.size(); count++){
String index = maxNodelist.get(count);
String[] indexAry = index.split(",");
int i = Integer.valueOf(indexAry[0]);
int j = Integer.valueOf(indexAry[1]);
ArrayList<ArrayList<String>> list = backTrack(x, y, i, j);
for(int counter=0; counter<list.get(0).size(); counter++){
outputSet.add(list.get(0).get(counter) +"," + list.get(1).get(counter) + "," + list.get(2).get(counter));
}
}
//Print all possible results
System.out.println("--- Output ---");
System.out.println("Max. length = " + len[x.length()][y.length()]);
for(String s: outputSet){
String[] ary = s.split(",");
System.out.println("LCS: " + ary[0] + " , in X: " + ary[1] + " , in Y: " + ary[2]);
}
}
/**
* Set the DP matrix
**/
private static void dpMatrix(String s1, String s2) {
for (int i = 1; i <=s1.length(); i++) {
for (int j = 1; j <=s2.length(); j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
len[i][j] = len[i-1][j-1] + 1;
type[i][j] = 1;
}else{
if(len[i-1][j] != len[i][j-1]){
if(len[i-1][j] > len[i][j-1]){
len[i][j] = len[i-1][j];
type[i][j] = 2;
}else{
len[i][j] = len[i][j-1];
type[i][j] = 3;
}
}else{
//if equal, set is as case 4
len[i][j] = len[i][j-1];
type[i][j] = 4;
}
}
if(len[i][j] > maxLength){
maxNodelist.clear();
maxLength = len[i][j];
maxNodelist.add(i + "," + j);
}else if(len[i][j] == maxLength){
maxNodelist.add(i + "," + j);
}
}// End of for
}// End of for
}
/**
* Backtrack from (i, j). Find out LCS and record the location of the strings respectively
* @param s1 1st string
* @param s2 2nd string
* @param i row index in the matrix
* @param j column index in the matrix
* @return ArrayList<ArrayList<String>>, outer ArrayList collect three inner ArrayList in order: LCS string, 1st string LCS location, 2nd string LCS location
*/
private static ArrayList<ArrayList<String>> backTrack(String s1, String s2, int i, int j){
if (i == 0 || j == 0) {
ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
ArrayList<String> lcsList = new ArrayList<String>();
ArrayList<String> xList = new ArrayList<String>();
ArrayList<String> yList = new ArrayList<String>();
lcsList.add("");
xList.add("");
yList.add("");
list.add(lcsList);
list.add(xList);
list.add(yList);
return list;
}
if(type[i][j]==1){
ArrayList<ArrayList<String>> resultList = new ArrayList<ArrayList<String>>();
ArrayList<String> resultLcsList = new ArrayList<String>();
ArrayList<String> resultXList = new ArrayList<String>();
ArrayList<String> resultYList = new ArrayList<String>();
ArrayList<ArrayList<String>> list = backTrack(s1, s2, i - 1, j - 1);
ArrayList<String> lcsList = list.get(0);
ArrayList<String> xList = list.get(1);
ArrayList<String> yList = list.get(2);
for(String s: lcsList){
resultLcsList.add(s + s1.charAt(i - 1));
}
for(String s: xList){
resultXList.add(s + " " + i);
}
for(String s: yList){
resultYList.add(s + " " + j);
}
resultList.add(resultLcsList);
resultList.add(resultXList);
resultList.add(resultYList);
return resultList;
}else if(type[i][j]==2){
ArrayList<ArrayList<String>> list = backTrack(s1,s2, i-1, j);
return list;
}else if(type[i][j]==3){
ArrayList<ArrayList<String>> list = backTrack(s1,s2, i, j-1);
return list;
}else{
ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
list = backTrack(s1,s2, i-1, j);
ArrayList<ArrayList<String>> case3list = backTrack(s1,s2, i, j-1);
ArrayList<String> lcsList = list.get(0);
ArrayList<String> xList = list.get(1);
ArrayList<String> yList = list.get(2);
lcsList.addAll(case3list.get(0));
xList.addAll(case3list.get(1));
yList.addAll(case3list.get(2));
list.set(0, lcsList);
list.set(1, xList);
list.set(2, yList);
return list;
}
}
}
1 ответ
Я обновил ваш код для визуализации змей (путь к найденному LCS), чтобы использовать тип интерфейса List вместо конкретного объекта ArrayList и придал значениям направления немного больше смысла, используя перечисление вместо значения int.
Возможно, это не лучший код, который я когда-либо писал, но он выполняет работу по визуализации найденных змей:
package lcs;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
/**
* <p>
* Longest common subsequecne finds the longest subsequence common to all
* sequences in a set of sequences. A subsequence in contrast to a substring
* does not have to consist of consecutive terms.
* </p>
*/
public class LCSMain
{
//test case
private static String x = "AACADBCDADCB";
private static String y = "DCACDCBBDBAD";
/** The maximum length of the longest common subsequences found **/
private static int maxLength = 0;
/** will hold a reference to the (i,j) nodes with match the length of the
* longest common subsequence **/
private static List<String> maxNodelist = new ArrayList<>();
/** will hold a form of heightfield that indicates the length of a
* subsequence which is reachable from this position **/
private static int[][] len = null;
/** will hold the direction values to backtrack the longest common
* subsequences **/
private static Direction[][] type = null;
private static TreeSet<String> outputSet = new TreeSet<>();
/**
* <p>
* Entrance point for the application. It will find the longest common
* subsequences (LCS) between <em>AACADBCDADCB</em> and <em>DCACDCBBDBAD</em>
* and print a graphical representation of the snakes (=path for a LCS) found
* as well as a listing of the found LCS and their positions within the
* original strings.
* </p>
*
* @param args The arguments passed to the application. Unused.
*/
public static void main (String[] args)
{
len = new int[x.length()+1][y.length()+1];
type = new Direction[x.length()+1][y.length()+1];
dpMatrix(x,y);
//Backtrack all possible LCS and add the results into outputSet
for(int count=0; count< maxNodelist.size(); count++)
{
String index = maxNodelist.get(count);
String[] indexAry = index.split(",");
int i = Integer.valueOf(indexAry[0]);
int j = Integer.valueOf(indexAry[1]);
List<List<String>> list = backTrack(x, y, i, j);
for(int counter=0; counter<list.get(0).size(); counter++)
{
outputSet.add(list.get(0).get(counter) +","
+ list.get(1).get(counter) + ","
+ list.get(2).get(counter));
}
}
// visualize the maximum length of a longest common subsequence
// accessible from any point in the matrix
printHeightField();
// visualize the path's found for the longest common subsequences
printSnake();
//Print all possible results
System.out.println("--- Output ---");
System.out.println("Max. length = " + len[x.length()][y.length()]);
for(String s: outputSet)
{
String[] ary = s.split(",");
System.out.println("LCS: " + ary[0] + ", in X: "
+ ary[1] + ", in Y: " + ary[2]);
}
}
/**
* <p>
* Prints the different subsequences into a matrix which contains the
* calculated direction values.
* </p>
*/
private static void printSnake()
{
// fill a char matrix with direction values
char[][] matrix = createDirectionMatrix();
// add path information to the matrix
for (String node : maxNodelist)
{
String[] indexAry = node.split(",");
int i = Integer.valueOf(indexAry[0]);
int j = Integer.valueOf(indexAry[1]);
backtrackPath(matrix, i, j);
}
// print the matrix
System.out.println("Snakes:");
System.out.println(printMatrix(matrix));
}
/**
* <p>
* Adds backtracking information to the direction matrix.
* </p>
*
* @param matrix The matrix to update with path informations
* @param i row index in the type matrix
* @param j column index in the type matrix
*/
private static void backtrackPath(char[][] matrix, int i, int j)
{
if (i==0 || j==0)
return;
// convert the index to matrix coordinates
int line = j*2+2;
int col = i*2+3;
// check which direction we need to follow
if (Direction.EQUALS.equals(type[i][j]))
{
matrix[line-1][col-1] = '\\';
backtrackPath(matrix, i-1, j-1);
}
else if (Direction.LEFT.equals(type[i][j]))
{
matrix[line][col-1] = '-';
backtrackPath(matrix, i-1, j);
}
else if (Direction.TOP.equals(type[i][j]))
{
matrix[line-1][col] = '|';
backtrackPath(matrix, i, j-1);
}
else
{
// split the path in both direction: to the left and to the top
matrix[line][col-1] = '-';
backtrackPath(matrix, i-1, j);
matrix[line-1][col] = '|';
backtrackPath(matrix, i, j-1);
}
}
/**
* <p>
* Creates an output matrix for the specified words containing the direction
* values as matrix data.
* </p>
*
* @return The created matrix containing direction values for the longest
* common subsequences
*/
private static char[][] createDirectionMatrix()
{
char[][] matrix = new char[2+type.length*2-1][];
for (int i=0; i<matrix.length; i++)
matrix[i] = new char[2+type.length*2];
// build the output matrix
for (int line=0; line<matrix.length; line++)
{
// The header column
if (line == 0)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 3)
matrix[line][col] = '^';
else if (col == 1)
matrix[line][col] = '|';
// empty column
else if (col % 2 == 0)
matrix[line][col] = ' ';
else if (col > 4)
{
matrix[line][col] = x.charAt(col / 2 - 2);
}
}
}
else if (line == 1)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 1)
matrix[line][col] = '+';
else
matrix[line][col] = '-';
}
}
// empty line
else if (line % 2 != 0)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 1)
matrix[line][col] = '|';
else
matrix[line][col] = ' ';
}
}
// border-line - 0 values, ^ indicates the start of the word
else if (line == 2)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 0)
matrix[line][col] = '^';
else if (col == 1)
matrix[line][col] = '|';
else if (col % 2 == 0)
matrix[line][col] = ' ';
else if (col > 2)
matrix[line][col] = '0';
}
}
// first column is the letter of the second word followed by
// space, delimiter, a further space and the direction value
else
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 0)
{
char c = y.charAt(line/2-2);
matrix[line][col] = c;
}
else if (col == 1)
matrix[line][col] = '|';
else if (col == 3)
matrix[line][col] = '0';
else if (col % 2 == 0)
matrix[line][col] = ' ';
else
{
int val = type[col/2-2+1][line/2-2+1].getValue();
matrix[line][col] = (char)('0'+val);
}
}
}
}
return matrix;
}
/**
* <p>
* Prints the content of the matrix containing the length values. The output
* will contain a heightmap like structure containing isoquants indicating
* the area where all subsequences have the same length.
* </p>
*/
private static void printHeightField()
{
System.out.println("Height-Field:");
System.out.println(printMatrix(createLengthMatrix()));
}
/**
* <p>
* Creates an output matrix for the specified words containing length values
* for each character couple. The specific value of each character couple
* marks the length of a subsequence which is reachable from this position.
* </p>
*
* @return
*/
private static char[][] createLengthMatrix()
{
char[][] matrix = new char[2+type.length*2-1][];
for (int i=0; i<matrix.length; i++)
matrix[i] = new char[2+type.length*2];
// build the output matrix
for (int line=0; line<matrix.length; line++)
{
// The header column
if (line == 0)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 3)
matrix[line][col] = '^';
else if (col == 1)
matrix[line][col] = '|';
// empty column
else if (col % 2 == 0)
matrix[line][col] = ' ';
else if (col > 4)
{
matrix[line][col] = x.charAt(col / 2 - 2);
}
}
}
else if (line == 1)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 1)
matrix[line][col] = '+';
else
matrix[line][col] = '-';
}
}
// empty line
else if (line % 2 != 0)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 1)
matrix[line][col] = '|';
else
{
matrix[line][col] = ' ';
}
}
}
// border-line - 0 values, ^ indicates the start of the word
else if (line == 2)
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 0)
matrix[line][col] = '^';
else if (col == 1)
matrix[line][col] = '|';
else if (col % 2 == 0)
matrix[line][col] = ' ';
else if (col > 2)
matrix[line][col] = '0';
}
}
// first column is the letter of the second word followed by
// space, delimiter, a further space and the direction value
else
{
for (int col = 0; col < matrix[line].length; col++)
{
if (col == 0)
{
char c = y.charAt(line/2-2);
matrix[line][col] = c;
}
else if (col == 1)
matrix[line][col] = '|';
else if (col == 3)
matrix[line][col] = '0';
else if (col % 2 == 0)
{
// check if the char to the left and to the top are
// delimiters, if so close it
if (matrix[line-2][col] == '|'
&& matrix[line-1][col-1] == '-')
matrix[line-1][col] = '+';
else
matrix[line][col] = ' ';
}
else
{
int x = col/2-2+1;
int y = line/2-2+1;
int val = len[x][y];
// check if the value to the left is lower than the
// actual value - insert a separator if so
if (x > 0)
{
if (len[x-1][y] < val)
{
// as we only write the length values every
// second line we need to fill the previous line
// too, else we have a gap in between
matrix[line-1][col-1] = '|';
matrix[line][col-1] = '|';
}
}
// check if the value to the top is lower than the
// actual value - insert a separator if so
if (y > 0)
{
if (len[x][y-1] < val)
{
// as we only write the length values every
// second column we need to fill the previous
// column too, else we have a gap in between
matrix[line-1][col] = '-';
matrix[line-1][col-1] = '-';
}
}
// connect left and top separators
if (matrix[line-1][col] == '-'
&& matrix[line][col-1] == '|')
matrix[line-1][col-1] = '+';
matrix[line][col] = (char)('0'+val);
}
}
}
}
return matrix;
}
/**
* <p>
* Returns the content of the direction matrix as a single {@link String}.
* </p>
*
* @param matrix The matrix to convert to String
* @return The String containing the direction values for the longest common
* subsequences
*/
private static String printMatrix(char[][] matrix)
{
StringBuilder sb = new StringBuilder();
for (int line = 0; line < matrix.length; line++)
{
for (int col = 0; col < matrix[line].length; col++)
{
sb.append(matrix[line][col]);
}
sb.append("\n");
}
return sb.toString();
}
/**
* Set the DP matrix
*
* <p>
* Fills two matrices and a list of nodes that achieved the maximum length
* for subsequences. The first matrix, <code>len</code> contains the maximum
* length a subsequence can achieve for each position. The second matrix,
* <code>type</code>, contains a direction pointer for backtracking.
* </p>
* <p>
* The filed list of nodes will contain the end nodes which achieved the
* greatest length value for a subsequence.
* </p>
*
* @param s1 The first string
* @param s2 The second string
**/
private static void dpMatrix(String s1, String s2)
{
for (int i = 1; i <= s1.length(); i++)
{
for (int j = 1; j <= s2.length(); j++)
{
// check if the characters match
if (s1.charAt(i-1) == s2.charAt(j-1))
{
len[i][j] = len[i-1][j-1] + 1;
type[i][j] = Direction.EQUALS;
}
else
{
// no match
// check if the value to the left is larger then the
// value to the top
if(len[i-1][j] > len[i][j-1])
{
len[i][j] = len[i-1][j];
type[i][j] = Direction.LEFT;
}
// is value to the top larger than the left one?
else if (len[i-1][j] < len[i][j-1])
{
len[i][j] = len[i][j-1];
type[i][j] = Direction.TOP;
}
else
{
// both values, the left one and the top one are
// identical so it does not matter which value we are
// taking later on
len[i][j] = len[i][j-1];
type[i][j] = Direction.SPLIT;
}
}
// save the end-nodes that achieve the longest commong
// subsequence
if(len[i][j] > maxLength)
{
maxNodelist.clear();
maxLength = len[i][j];
maxNodelist.add(i + "," + j);
}
else if(len[i][j] == maxLength)
{
maxNodelist.add(i + "," + j);
}
}// End of for
}// End of for
}
/**
* <p>
* Backtrack from (i, j). Find out LCS and record the location of the
* strings respectively
* </p>
*
* @param s1 1st string
* @param s2 2nd string
* @param i row index in the matrix
* @param j column index in the matrix
* @return List<List<String>>, outer List collect three inner List in order:
* LCS string, 1st string LCS location, 2nd string LCS location
*/
private static List<List<String>> backTrack(String s1, String s2, int i, int j)
{
if (i == 0 || j == 0)
{
List<List<String>> list = new ArrayList<>();
List<String> lcsList = new ArrayList<>();
List<String> xList = new ArrayList<>();
List<String> yList = new ArrayList<>();
lcsList.add("");
xList.add("");
yList.add("");
list.add(lcsList);
list.add(xList);
list.add(yList);
return list;
}
if(Direction.EQUALS.equals(type[i][j]))
{
List<List<String>> resultList = new ArrayList<>();
List<String> resultLcsList = new ArrayList<>();
List<String> resultXList = new ArrayList<>();
List<String> resultYList = new ArrayList<>();
List<List<String>> list = backTrack(s1, s2, i - 1, j - 1);
List<String> lcsList = list.get(0);
List<String> xList = list.get(1);
List<String> yList = list.get(2);
for(String s: lcsList)
{
resultLcsList.add(s + s1.charAt(i - 1));
}
for(String s: xList)
{
resultXList.add(s + " " + i);
}
for(String s: yList)
{
resultYList.add(s + " " + j);
}
resultList.add(resultLcsList);
resultList.add(resultXList);
resultList.add(resultYList);
return resultList;
}
else if(Direction.LEFT.equals(type[i][j]))
{
List<List<String>> list = backTrack(s1, s2, i-1, j);
return list;
}
else if(Direction.TOP.equals(type[i][j]))
{
List<List<String>> list = backTrack(s1, s2, i, j-1);
return list;
}
else
{
// backtrack to the left
List<List<String>> leftMove = backTrack(s1, s2, i-1, j);
// backtrack to the top
List<List<String>> topMove = backTrack(s1, s2, i, j-1);
List<String> lcsList = leftMove.get(0);
List<String> xList = leftMove.get(1);
List<String> yList = leftMove.get(2);
lcsList.addAll(topMove.get(0));
xList.addAll(topMove.get(1));
yList.addAll(topMove.get(2));
return leftMove;
}
}
}
И добавленное перечисление, чтобы дать направлениям немного больше семантики:
package lcs;
/**
* <p>
* Enumeration of the possible direction for backtracking.
* </p>
*/
public enum Direction
{
/** will result in a single move to the top as well as to the left **/
EQUALS(1),
/** will result in a move to the left **/
LEFT(2),
/** will result in a move to the top **/
TOP(3),
/** will result in splitting the move to follow both directions at once:
* to the left and to the top **/
SPLIT(4);
/** will hold an int value representing the defined direction **/
private final int value;
/**
* <p>
* Initializes the enumeration value with an int-value.
* </p>
*
* @param value The int value to assign to the enumeration value
*/
private Direction(int value)
{
this.value = value;
}
/**
* <p>
* Returns the int representation of the corresponding enumeration.
* </p>
*
* @return The int value of this enumeration value
*/
public int getValue()
{
return this.value;
}
}
Выполнение этого приложения приведет к следующему выводу:
Height-Field:
| ^ A A C A D B C D A D C B
-+--------------------------
^| 0 0 0 0 0 0 0 0 0 0 0 0 0
| +---------------
D| 0 0 0 0 0|1 1 1 1 1 1 1 1
| +---+ +-----------
C| 0 0 0|1 1 1 1|2 2 2 2 2 2
| +---+ +-----+ +-------
A| 0|1 1 1|2 2 2 2 2|3 3 3 3
| | +-+ +---+ +---
C| 0|1 1|2 2 2 2|3 3 3 3|4 4
| | | +---+ +-----+
D| 0|1 1|2 2|3 3 3|4 4 4 4 4
| | | | +-+ +---
C| 0|1 1|2 2|3 3|4 4 4 4|5 5
| | | | +-+ | +-
B| 0|1 1|2 2|3|4 4 4 4 4|5|6
| | | | | | |
B| 0|1 1|2 2|3|4 4 4 4 4|5|6
| | | | | +-----+ |
D| 0|1 1|2 2|3|4 4|5 5 5 5|6
| | | | | | |
B| 0|1 1|2 2|3|4 4|5 5 5 5|6
| | +-+ +-+ | | +-----+
A| 0|1|2 2|3 4|4 4|5|6 6 6 6
| | | | +-+ | | +-----
D| 0|1|2 2|3|4 4 4|5|6|7 7 7
Snakes:
| ^ A A C A D B C D A D C B
-+--------------------------
^| 0 0 0 0 0 0 0 0 0 0 0 0 0
| | |
D| 0-4-4 4 4 1 2 2 1 2 1 2 2
| | \
C| 0-4 4 1 2 4 4 1 2 2 2 1 2
| \ \
A| 0 1 1 4 1 2 2 4 4 1 2 2 2
| \ |
C| 0 3 4 1-4 4 4 1 2 4 4 1 2
| \
D| 0 3 4 3 4 1-2 4 1 2 1 4 4
| | \
C| 0 3 4 1 4 3 4 1 4 4 4 1 2
| |\ |
B| 0 3 4 3 4 3 1-4 4 4 4 3 1
| \ |
B| 0 3 4 3 4 3 1-4 4 4 4 3 1
| \
D| 0 3 4 3 4 1 3 4 1 2 1 4 3
| |
B| 0 3 4 3 4 3 1 4 3 4 4 4 1
| \
A| 0 1 1 4 1 4 3 4 3 1 2 2 4
| \
D| 0 3 3 4 3 1 4 4 1 3 1-2-2
--- Output ---
Max. length = 7
LCS: ACDBDAD, in X: 2 3 5 6 8 9 10, in Y: 3 4 5 7 9 11 12
LCS: ACDBDAD, in X: 2 3 5 6 8 9 10, in Y: 3 4 5 8 9 11 12
LCS: ACDCDAD, in X: 2 3 5 7 8 9 10, in Y: 3 4 5 6 9 11 12
LCS: CADBDAD, in X: 3 4 5 6 8 9 10, in Y: 2 3 5 7 9 11 12
LCS: CADBDAD, in X: 3 4 5 6 8 9 10, in Y: 2 3 5 8 9 11 12
LCS: CADCDAD, in X: 3 4 5 7 8 9 10, in Y: 2 3 5 6 9 11 12
Так что 6 решений кажутся мне вполне правдоподобными. Как уже упоминалось в моем комментарии, пожалуйста, опубликуйте свои 2 отсутствующих решения, чтобы мы могли оценить, являются ли они ошибочными или почему они не появляются в результатах вашего dpMatrix() метод.