algorithm - predictivo - teclado para marcar teléfono
Genera un número de 10 dígitos usando el teclado de un teléfono (12)
Claro que se puede hacer en tiempo polinomial. Es un excelente ejercicio en programación dinámica o memoization .
Supongamos que N (el número de dígitos) es igual a 10 para el ejemplo.
Piense en esto recursivamente así: ¿Cuántos números puedo construir usando 10 dígitos comenzando desde 1 ?
La respuesta es
[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].
Entonces, ¿cuántos "números de 9 dígitos que comienzan con 8" hay? Bien,
[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]
y así. Se llega al caso base cuando se obtiene la pregunta "¿Cuántos números de 1 dígito hay a partir de X " (y la respuesta es obviamente 1)?
Cuando se trata de complejidad, la observación clave es que reutiliza soluciones previamente computadas. Eso es, por ejemplo, la respuesta a "cuántos números de 5 dígitos que comienzan con 3 " puede usarse tanto al responder "cuántos números de 6 dígitos hay a partir de 8 " Y "cuántos números de 6 dígitos hay allí a partir de 4 " . Esta reutilización hace que la complejidad colapse de exponencial a polinomial.
Veamos más de cerca la complejidad de una solución de programación dinámica:
Dicha implementación llenaría una matriz de la siguiente manera:
num[1][i] = 1, for all 0<=i<=9 -- there are one 1-digit number starting from X.
for digits = 2...N
for from = 0...9
num[digits][from] = num[digits-1][successor 1 of from] +
num[digits-1][successor 2 of from] +
...
num[digits-1][successor K of from]
return num[N][1] -- number of N-digit numbers starting from 1.
El algoritmo simplemente llena la matriz una celda a la vez, y la matriz es de dimensión 10 * N y, por lo tanto, se ejecuta en tiempo lineal .
Lo escribí desde la parte superior de mi cabeza, corríjame si hay errores tipográficos.
Dado un teclado de teléfono como se muestra a continuación:
1 2 3
4 5 6
7 8 9
0
¿Cuántos números diferentes de 10 dígitos se pueden formar a partir de 1? La restricción es que el movimiento de 1 dígito al siguiente es similar al movimiento del Caballero en un juego de ajedrez.
Por ejemplo. si estamos en 1, el siguiente dígito puede ser 6 u 8, si estamos en 6, el siguiente dígito puede ser 1, 7 o 0.
Se permite la repetición de dígitos: 1616161616 es un número válido.
¿Existe un algoritmo de tiempo polinomial que resuelva este problema? El problema requiere que solo contemos los números de 10 dígitos y no necesariamente listemos los números.
EDITAR: Intenté modelar esto como un gráfico con cada dígito teniendo 2 o 3 dígitos como sus vecinos. Luego usé DFS para navegar hasta la profundidad de 10 nodos y luego incrementar el conteo de números cada vez que llegué a la profundidad de 10. Esto obviamente no es tiempo polinomial. Suponiendo que cada dígito tuviera solo 2 vecinos, esto habría requerido al menos 2 ^ 10 iteraciones.
La variable aquí es el número de dígitos. He tomado el ejemplo. de números de 10 dígitos. También podría ser de n dígitos.
Decidí abordar este problema y hacerlo lo más extensible posible. Esta solución le permite:
Defina su propio tablero (teclado de teléfono, tablero de ajedrez, etc.)
Defina su propia pieza de ajedrez (Caballero, Torre, Obispo, etc.); Tendrá que escribir la clase concreta y generarla desde la fábrica.
Recupere varias piezas de información a través de algunos métodos de utilidad útiles.
Las clases son las siguientes:
PadNumber: Clase que define un botón en el teclado del teléfono. Podría ser renombrado a ''Cuadrado'' para representar un cuadrado de tablero.
ChessPiece: clase abstracta que define campos para todas las piezas de ajedrez.
Movimiento: interfaz que define los métodos de movimiento y permite la generación de piezas en fábrica.
PieceFactory: Clase de fábrica para generar piezas de ajedrez.
Knight: clase concreta que hereda de ChessPiece e implementa el movimiento
PhoneChess: Clase de entrada.
Conductor: Código del conductor.
OK, aquí está el código :)
package PhoneChess;
import java.awt.Point;
public class PadNumber {
private String number = "";
private Point coordinates = null;
public PadNumber(String number, Point coordinates)
{
if(number != null && number.isEmpty()==false)
this.number = number;
else
throw new IllegalArgumentException("Input cannot be null or empty.");
if(coordinates == null || coordinates.x < 0 || coordinates.y < 0)
throw new IllegalArgumentException();
else
this.coordinates = coordinates;
}
public String getNumber()
{
return this.number;
}
public Integer getNumberAsNumber()
{
return Integer.parseInt(this.number);
}
public Point getCoordinates()
{
return this.coordinates;
}
public int getX()
{
return this.coordinates.x;
}
public int getY()
{
return this.coordinates.y;
}
}
Pieza de ajedrez
package PhoneChess;
import java.util.HashMap;
import java.util.List;
public abstract class ChessPiece implements Movement {
protected String name = "";
protected HashMap<PadNumber, List<PadNumber>> moves = null;
protected Integer fullNumbers = 0;
protected int[] movesFrom = null;
protected PadNumber[][] thePad = null;
}
Interfaz de movimiento:
package PhoneChess;
import java.util.List;
public interface Movement
{
public Integer findNumbers(PadNumber start, Integer digits);
public abstract boolean canMove(PadNumber from, PadNumber to);
public List<PadNumber> allowedMoves(PadNumber from);
public Integer countAllowedMoves(PadNumber from);
}
PiezaFábrica
package PhoneChess;
public class PieceFactory
{
public ChessPiece getPiece(String piece, PadNumber[][] thePad)
{
if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
throw new IllegalArgumentException("Invalid pad");
if(piece == null)
throw new IllegalArgumentException("Invalid chess piece");
if(piece.equalsIgnoreCase("Knight"))
return new Knight("Knight", thePad);
else
return null;
}
}
Clase caballero
package PhoneChess;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public final class Knight extends ChessPiece implements Movement {
/**Knight movements
* One horizontal, followed by two vertical
* Or
* One vertical, followed by two horizontal
* @param name
*/
public Knight(String name, PadNumber[][] thePad)
{
if(name == null || name.isEmpty() == true)
throw new IllegalArgumentException("Name cannot be null or empty");
this.name = name;
this.thePad = thePad;
this.moves = new HashMap<>();
}
private Integer fullNumbers = null;
@Override
public Integer findNumbers(PadNumber start, Integer digits)
{
if(start == null || "*".equals(start.getNumber()) || "#".equals(start.getNumber()) ) { throw new IllegalArgumentException("Invalid start point"); }
if(start.getNumberAsNumber() == 5) { return 0; } //Consider adding an ''allowSpecialChars'' condition
if(digits == 1) { return 1; };
//Init
this.movesFrom = new int[thePad.length * thePad[0].length];
for(int i = 0; i < this.movesFrom.length; i++)
this.movesFrom[i] = -1;
fullNumbers = 0;
findNumbers(start, digits, 1);
return fullNumbers;
}
private void findNumbers(PadNumber start, Integer digits, Integer currentDigits)
{
//Base condition
if(currentDigits == digits)
{
//Reset
currentDigits = 1;
fullNumbers++;
return;
}
if(!this.moves.containsKey(start))
allowedMoves(start);
List<PadNumber> options = this.moves.get(start);
if(options != null)
{
currentDigits++; //More digits to be got
for(PadNumber option : options)
findNumbers(option, digits, currentDigits);
}
}
@Override
public boolean canMove(PadNumber from, PadNumber to)
{
//Is the moves list available?
if(!this.moves.containsKey(from.getNumber()))
{
//No? Process.
allowedMoves(from);
}
if(this.moves.get(from) != null)
{
for(PadNumber option : this.moves.get(from))
{
if(option.getNumber().equals(to.getNumber()))
return true;
}
}
return false;
}
/***
* Overriden method that defines each Piece''s movement restrictions.
*/
@Override
public List<PadNumber> allowedMoves(PadNumber from)
{
//First encounter
if(this.moves == null)
this.moves = new HashMap<>();
if(this.moves.containsKey(from))
return this.moves.get(from);
else
{
List<PadNumber> found = new ArrayList<>();
int row = from.getY();//rows
int col = from.getX();//columns
//Cases:
//1. One horizontal move each way followed by two vertical moves each way
if(col-1 >= 0 && row-2 >= 0)//valid
{
if(thePad[row-2][col-1].getNumber().equals("*") == false &&
thePad[row-2][col-1].getNumber().equals("#") == false)
{
found.add(thePad[row-2][col-1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col-1 >= 0 && row+2 < thePad.length)//valid
{
if(thePad[row+2][col-1].getNumber().equals("*") == false &&
thePad[row+2][col-1].getNumber().equals("#") == false)
{
found.add(thePad[row+2][col-1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col+1 < thePad[0].length && row+2 < thePad.length)//valid
{
if(thePad[row+2][col+1].getNumber().equals("*") == false &&
thePad[row+2][col+1].getNumber().equals("#") == false)
{
found.add(thePad[row+2][col+1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col+1 < thePad[0].length && row-2 >= 0)//valid
{
if(thePad[row-2][col+1].getNumber().equals("*") == false &&
thePad[row-2][col+1].getNumber().equals("#") == false)
found.add(thePad[row-2][col+1]);
}
//Case 2. One vertical move each way follow by two horizontal moves each way
if(col-2 >= 0 && row-1 >= 0)
{
if(thePad[row-1][col-2].getNumber().equals("*") == false &&
thePad[row-1][col-2].getNumber().equals("#") == false)
found.add(thePad[row-1][col-2]);
}
if(col-2 >= 0 && row+1 < thePad.length)
{
if(thePad[row+1][col-2].getNumber().equals("*") == false &&
thePad[row+1][col-2].getNumber().equals("#") == false)
found.add(thePad[row+1][col-2]);
}
if(col+2 < thePad[0].length && row-1 >= 0)
{
if(thePad[row-1][col+2].getNumber().equals("*") == false &&
thePad[row-1][col+2].getNumber().equals("#") == false)
found.add(thePad[row-1][col+2]);
}
if(col+2 < thePad[0].length && row+1 < thePad.length)
{
if(thePad[row+1][col+2].getNumber().equals("*") == false &&
thePad[row+1][col+2].getNumber().equals("#") == false)
found.add(thePad[row+1][col+2]);
}
if(found.size() > 0)
{
this.moves.put(from, found);
this.movesFrom[from.getNumberAsNumber()] = found.size();
}
else
{
this.moves.put(from, null); //for example the Knight cannot move from 5 to anywhere
this.movesFrom[from.getNumberAsNumber()] = 0;
}
}
return this.moves.get(from);
}
@Override
public Integer countAllowedMoves(PadNumber from)
{
int start = from.getNumberAsNumber();
if(movesFrom[start] != -1)
return movesFrom[start];
else
{
movesFrom[start] = allowedMoves(from).size();
}
return movesFrom[start];
}
@Override
public String toString()
{
return this.name;
}
}
PhoneChess clase entrante
package PhoneChess;
public final class PhoneChess
{
private ChessPiece thePiece = null;
private PieceFactory factory = null;
public ChessPiece ThePiece()
{
return this.thePiece;
}
public PhoneChess(PadNumber[][] thePad, String piece)
{
if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
throw new IllegalArgumentException("Invalid pad");
if(piece == null)
throw new IllegalArgumentException("Invalid chess piece");
this.factory = new PieceFactory();
this.thePiece = this.factory.getPiece(piece, thePad);
}
public Integer findPossibleDigits(PadNumber start, Integer digits)
{
if(digits <= 0)
throw new IllegalArgumentException("Digits cannot be less than or equal to zero");
return thePiece.findNumbers(start, digits);
}
public boolean isValidMove(PadNumber from, PadNumber to)
{
return this.thePiece.canMove(from, to);
}
}
Código del conductor:
public static void main(String[] args) {
PadNumber[][] thePad = new PadNumber[4][3];
thePad[0][0] = new PadNumber("1", new Point(0,0));
thePad[0][1] = new PadNumber("2", new Point(1,0));
thePad[0][2] = new PadNumber("3",new Point(2,0));
thePad[1][0] = new PadNumber("4",new Point(0,1));
thePad[1][1] = new PadNumber("5",new Point(1,1));
thePad[1][2] = new PadNumber("6", new Point(2,1));
thePad[2][0] = new PadNumber("7", new Point(0,2));
thePad[2][1] = new PadNumber("8", new Point(1,2));
thePad[2][2] = new PadNumber("9", new Point(2,2));
thePad[3][0] = new PadNumber("*", new Point(0,3));
thePad[3][1] = new PadNumber("0", new Point(1,3));
thePad[3][2] = new PadNumber("#", new Point(2,3));
PhoneChess phoneChess = new PhoneChess(thePad, "Knight");
System.out.println(phoneChess.findPossibleDigits(thePad[0][1],4));
}
}
El método devuelve la lista de números de 10 dígitos que comienzan con 1. Una vez más, el conteo es 1424.
public ArrayList<String> getList(int digit, int length, String base ){
ArrayList<String> list = new ArrayList<String>();
if(length == 1){
list.add(base);
return list;
}
ArrayList<String> temp;
for(int i : b[digit]){
String newBase = base +i;
list.addAll(getList(i, length -1, newBase ));
}
return list;
}
Enfoque de la memoria recursiva:
vector<vector<int>> lupt = { {4, 6}, {6, 8}, {9, 7}, {4, 8}, {3, 9, 0},
{}, {1,7,0}, {6, 2}, {1, 3}, {2, 4} };
int numPhoneNumbersUtil(int startdigit, int& phonenumberlength, int currCount, map< pair<int,int>,int>& memT)
{
int noOfCombs = 0;
vector<int> enddigits;
auto it = memT.find(make_pair(startdigit,currCount));
if(it != memT.end())
{
noOfCombs = it->second;
return noOfCombs;
}
if(currCount == phonenumberlength)
{
return 1;
}
enddigits = lupt[startdigit];
for(auto it : enddigits)
{
noOfCombs += numPhoneNumbersUtil(it, phonenumberlength, currCount + 1, memT);
}
memT.insert(make_pair(make_pair(startdigit,currCount), noOfCombs));
return memT[make_pair(startdigit,currCount)];
}
int numPhoneNumbers(int startdigit, int phonenumberlength)
{
map<pair<int,int>,int> memT;
int currentCount = 1; //the first digit has already been added
return numPhoneNumbersUtil(startdigit, phonenumberlength, currentCount, memT);
}
Este problema también se puede modelar como un problema de satisfacción de restricciones (también conocido como CSP).
Sugiero usar el solucionador Minion (rápido y escalable) que puedes encontrar here .
Modelar tal vez tedioso y consumir tiempo (curva de aprendizaje pronunciada).
En lugar de utilizar la información del lenguaje Minion, mi consejo es formular el modelo con un lenguaje de modelado independiente de solucionador como ESSENCE y encontrar un convertidor en consecuencia.
Esto se puede hacer en O (log N). Considere el teclado y los posibles movimientos en él como un gráfico G (V, E) donde los vértices son los dígitos disponibles y los bordes indican qué dígitos pueden seguir a cuál. Ahora, para cada posición de salida i podemos formar un vector Trayectorias (i) que contienen el número de rutas diferentes a las que se puede llegar en cada vértice. Ahora es bastante fácil ver que, para una posición dada i y un dígito v , las rutas posibles pueden se puede alcanzar a través de la suma de las diferentes rutas a las que se podría llegar a los dígitos anteriores anteriores, o Rutas (i) [v] = suma (Rutas (i-1) [v2] * (1 if (v, v2) en E de lo contrario 0) para v2 en V) . Ahora, esto es tomar la suma de cada posición en el vector anterior por una posición correspondiente en una columna de la matriz de adyacencia. Así que podemos simplificar esto como Rutas (i) = Rutas (i-1) · A , donde A es la matriz de adyacencia de la gráfica. Al deshacerse de la recursión y aprovechar la asociatividad de la multiplicación de matrices, esto se convierte en Rutas (i) = Rutas (1) · A ^ (i-1) . Conocemos las rutas (1) : solo tenemos una ruta, al dígito 1.
El número total de rutas para un n dígitos es la suma de las rutas para cada dígito, por lo que el algoritmo final se convierte en: TotalPaths (n) = suma ([1,0,0,0,0,0,0,0, 0,0] · A ^ (n-1))
La exponenciación se puede calcular mediante la cuadratura en tiempo O (log (n)) , dado el tiempo constante multiplicado, de lo contrario O (M (n) * log (n)) donde M (n) es la complejidad de su algoritmo favorito de multiplicación de precisión arbitraria para números de n dígitos.
Función recursiva en Java:
public static int countPhoneNumbers (int n, int r, int c) {
if (outOfBounds(r,c)) {
return 0;
} else {
char button = buttons[r][c];
if (button == ''.'') {
// visited
return 0;
} else {
buttons[r][c] = ''.''; // record this position so don''t revisit.
// Count all possible phone numbers with one less digit starting
int result=0;
result = countPhoneNumbers(n-1,r-2,c-1)
+ countPhoneNumbers(n-1,r-2,c+1)
+ countPhoneNumbers(n-1,r+2,c-1)
+ countPhoneNumbers(n-1,r+2,c+1)
+ countPhoneNumbers(n-1,r-1,c-2)
+ countPhoneNumbers(n-1,r-1,c+2)
+ countPhoneNumbers(n-1,r+1,c-2)
+ countPhoneNumbers(n-1,r+1,c+2);
}
buttons[r][c] = button; // Remove record from position.
return result;
}
}
}
Implementé fuerza bruta y modelos de programación dinámica.
import queue
def chess_numbers_bf(start, length):
if length <= 0:
return 0
phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
total = 0
q = queue.Queue()
q.put((start, 1))
while not q.empty():
front = q.get()
val = front[0]
len_ = front[1]
if len_ < length:
for elm in phone[val]:
q.put((elm, len_ + 1))
else:
total += 1
return total
def chess_numbers_dp(start, length):
if length <= 0:
return 0
phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
memory = {}
def __chess_numbers_dp(s, l):
if (s, l) in memory:
return memory[(s, l)]
elif l == length - 1:
memory[(s, l)] = 1
return 1
else:
total_n_ways = 0
for number in phone[s]:
total_n_ways += __chess_numbers_dp(number, l+1)
memory[(s, l)] = total_n_ways
return total_n_ways
return __chess_numbers_dp(start, 0)
# bf
for i in range(0, 10):
print(i, chess_numbers_bf(3, i))
print(''/n'')
for i in range(0, 10):
print(i, chess_numbers_bf(9, i))
print(''/n'')
# dp
for i in range(0, 10):
print(i, chess_numbers_dp(3, i))
print(''/n'')
# dp
for i in range(0, 10):
print(i, chess_numbers_dp(9, i))
print(''/n'')
No estoy seguro de si me perdí algo, pero al leer la descripción del problema llegué a esta solución. Tiene complejidad de tiempo O (n) y complejidad de espacio O (1).
Me di cuenta de que el número 1 está en una esquina, ¿verdad? En cada esquina puede moverse a uno de los lados (4 de 9 y 3, o 6 de 7 a 1) o uno de los lados "verticales" (8 de 3 y 1, o 2 de 9 y 7). Entonces, las esquinas agregan dos movimientos: un movimiento lateral y un movimiento ''vertical''. Esto es cierto para las cuatro esquinas (1,3,9,7).
Desde cada lado, puedes moverte a dos esquinas (7 y 1 de 6, 9 y 3 de 4) o puedes llegar a la tecla inferior (0). Son tres movimientos. Dos esquinas y un fondo.
En la tecla inferior (0), puede moverse a ambos lados (4 y 6). Entonces, en cada paso, verifica todos los finales posibles para la ruta de la longitud anterior (es decir, cuántos terminaron en una esquina, un lado, una tecla cero ''vertical'' o ''inferior'') y luego generan un nuevo final Cuenta de acuerdo a las reglas de generación indicadas anteriormente.
- Cada extremo de esquina agrega un lado y una vertical.
- Cada extremo lateral añade 2 esquinas y un fondo.
- Cada final vertical añade 2 esquinas.
- Cada final inferior agrega 2 lados.
Si comienza desde la tecla ''1'', comienza con una posible solución de esquina, en cada paso cuenta el número de finales de esquina, lateral, vertical e inferior del paso anterior y luego aplica las reglas para generar el siguiente conteo.
En código javascript plano.
function paths(n) {
//Index to 0
var corners = 1;
var verticals = 0;
var bottom = 0;
var sides = 0;
if (n <= 0) {
//No moves possible for paths without length
return 0;
}
for (var i = 1; i < n; i++) {
var previousCorners = corners;
var previousVerticals = verticals;
var previousBottom = bottom;
var previousSides = sides;
sides = 1 * previousCorners + 2 * previousBottom;
verticals = 1 * previousCorners;
bottom = 1 * previousSides;
corners = 2 * previousSides + 2 * previousVerticals;
//console.log("Moves: %d, Length: %d, Sides: %d, Verticals: %d, Bottom: %d, Corners: %d, Total: %d", i, i + 1, sides, verticals, bottom, corners, sides+verticals+bottom+corners);
}
return sides + verticals + bottom + corners;
}
for (var i = 0; i <= 10; i++) {
console.log(paths(i));
}
Tiempo de ejecución solución de tiempo constante:
#include <iostream>
constexpr int notValid(int x, int y) {
return !(( 1 == x && 3 == y ) || //zero on bottom.
( 0 <= x && 3 > x && //1-9
0 <= y && 3 > y ));
}
class Knight {
template<unsigned N > constexpr int move(int x, int y) {
return notValid(x,y)? 0 : jump<N-1>(x,y);
}
template<unsigned N> constexpr int jump( int x, int y ) {
return move<N>(x+1, y-2) +
move<N>(x-1, y-2) +
move<N>(x+1, y+2) +
move<N>(x-1, y+2) +
move<N>(x+2, y+1) +
move<N>(x-2, y+1) +
move<N>(x+2, y-1) +
move<N>(x-2, y-1);
}
public:
template<unsigned N> constexpr int count() {
return move<N-1>(0,1) + move<N-1>(0,2) +
move<N-1>(1,0) + move<N-1>(1,1) + move<N-1>(1,2) +
move<N-1>(2,0) + move<N-1>(2,1) + move<N-1>(2,2);
}
};
template<> constexpr int Knight::move<0>(int x, int y) { return notValid(x,y)? 0 : 1; }
template<> constexpr int Knight::count<0>() { return 0; } //terminal cases.
template<> constexpr int Knight::count<1>() { return 8; }
int main(int argc, char* argv[]) {
static_assert( ( 16 == Knight().count<2>() ), "Fail on test with 2 lenght" ); // prof of performance
static_assert( ( 35 == Knight().count<3>() ), "Fail on test with 3 lenght" );
std::cout<< "Number of valid Knight phones numbers:" << Knight().count<10>() << std::endl;
return 0;
}
Una respuesta más sencilla.
#include<stdio.h>
int a[10] = {2,2,2,2,3,0,3,2,2,2};
int b[10][3] = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};
int count(int curr,int n)
{
int sum = 0;
if(n==10)
return 1;
else
{
int i = 0;
int val = 0;
for(i = 0; i < a[curr]; i++)
{
val = count(b[curr][i],n+1);
sum += val;
}
return sum;
}
}
int main()
{
int n = 1;
int val = count(1,0);
printf("%d/n",val);
}
¡¡celebrar!!
//Both the iterative and recursive with memorize shows count as 1424 for 10 digit numbers starting with 1.
int[][] b = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};
public int countIterative(int digit, int length) {
int[][] matrix = new int[length][10];
for(int dig =0; dig <=9; dig++){
matrix[0][dig] = 1;
}
for(int len = 1; len < length; len++){
for(int dig =0; dig <=9; dig++){
int sum = 0;
for(int i : b[dig]){
sum += matrix[len-1][i];
}
matrix[len][dig] = sum;
}
}
return matrix[length-1][digit];
}
public int count(int index, int length, int[][] matrix ){
int sum = 0;
if(matrix[length-1][index] > 0){
System.out.println("getting value from memoize:"+index + "length:"+ length);
return matrix[length-1][index];
}
if( length == 1){
return 1;
}
for(int i: b[index] ) {
sum += count(i, length-1,matrix);
}
matrix[length-1][index] = sum;
return sum;
}