Проблем с мобилната цифрова клавиатура


Ниво на трудност Трудно
Често задавани в Амазонка Maq Microsoft Sprinklr
комбинаторен Динамично програмиране матрица Низ

Декларация за проблема

В проблема с мобилната цифрова клавиатура разглеждаме цифрова клавиатура. Трябва да намерим целия брой възможни цифрови последователности с дадена дължина, така че да имате право да натискате само бутони отгоре, надолу, отляво и отдясно на текущия бутон. Нямате право да натискате ъгловите бутони на долния ред (* (звезда) и # (хеш)), които са маркирани в сиво на изображението по-долу.

Цифрова клавиатура

Пример

1
10

Обяснение: Можете да използвате всички цифри (0 до 9), като по този начин допринасяте с 10 за отговора.

2
36

Обяснение: Помислете, че сте избрали 0, след което можете да изберете 0 и 8 като второ число.

Помислете, че сте избрали 1, след което можете да изберете 1, 2, 4 като второ число. По същия начин правим това за всички цифри.

 

Подход за проблем с мобилна цифрова клавиатура

Рекурсивен подход

За проблема с мобилната цифрова клавиатура първото нещо, което ми идва на ум, е рекурсивен подход. И така, можем да разрешим проблема рекурсивно такива, че ако сме в позиция i, j и имаме n числа, които да изберем, можем да се движим в посока нагоре (i-1, j), посока надолу (i + 1, j), лява посока (i, j-1 ), в дясна посока (i, j + 1) и останете на текущата позиция (i, j) с n-1 числа сега, от които да избирате. Този подход е абсолютно правилен, но не е достатъчно ефективен.

//Base Case
if (N = 1) return 10
else
    return sum of all findNumberOfSequences(i, j, n) where i,j is new position after a valid move from current position

Динамично програмиране

Когато се опитваме да разрешим проблема с мобилната цифрова клавиатура за дължината на числовата последователност, равна на n. Виждаме, че първоначалният проблем зависи от по-малки подпроблеми. Помислете за проблема, когато решаваме за n, равно на 3. Тогава можем да видим, че нашият проблем зависи от броя на последователностите с дължина, равна на 2. След това ще се движим в посока нагоре надолу посока наляво и надясно или ще останем на същото място, но тъй като заехме тази позиция (цифра) и добавихме за отговор. Проблемът е сведен до по-малък проблем с n = 2. Сега, ако видим, че сме започнали от цифра и сме се движили в разрешени посоки, тогава можем да видим, че имаме припокриващи се подпроблеми, така че това ни дава интуиция за използване динамично програмиране.

Като цяло в динамично програмиране, това, което правим е, че първо решаваме за по-малки проблеми и след това комбинираме резултатите от по-малки проблеми, за да решим първоначалния си проблем, така че какво ще правим, както ще решаваме за n, равно на 1, след това n равно на 2 и т.н.

код

C ++ код

#include <bits/stdc++.h> 
using namespace std;

int findNumberOfSequences(int n) 
{ 
  char keypad[4][3] = {{'1','2','3'}, 
                       {'4','5','6'}, 
                       {'7','8','9'}, 
                       {'*','0','#'}};
  
  //Base Case
  if(n <= 0) 
    return 0; 
  if(n == 1) 
    return 10; 

  //Directions to move to
  int dir[][2]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};

  //dp[i][j] = number of sequences of length j starting with digit i
  int dp[10][n+1];
  memset(dp,0, sizeof dp);
  
  // fill the numbers starting with digit i and of length 1 
  for(int i=0; i<=9; i++)
    dp[i][1] = 1;

  // Now solve problem for n=2,3,.. using smaller sub-problems
  for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
  { 
    for(int row=0; row<4; row++)
    { 
      for (int col=0; col<3; col++)
      { 
        if (keypad[row][col] != '*' && keypad[row][col] != '#') 
        { 
          //fixing the first digit
          int num = keypad[row][col] - '0';

          //Now select the remaining digit in sequence
          for(int step=0; step<5; step++) 
          { 
            int new_row = row + dir[step][0]; 
            int new_col = col + dir[step][1]; 
            if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
            && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
            { 
              int nextNum = keypad[new_row][new_col] - '0'; 
              dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
            } 
          } 
        } 
      } 
    } 
  } 

  // Add the number of sequences of length starting with digit i(0 to 9)
  int ans = 0; 
  for(int i=0; i<=9; i++) 
    ans += dp[i][n]; 
  return ans; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<"Number of sequences of length "<<n<<" = "<<findNumberOfSequences(n)<<endl;
  }
} 
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36 
Number of sequences of length 3 = 138 
Number of sequences of length 4 = 532 
Number of sequences of length 5 = 2062

 

Java код

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int findNumberOfSequences(int n) 
    { 
      	char keypad[][] = {{'1','2','3'}, 
    		           {'4','5','6'}, 
    	         	   {'7','8','9'}, 
    			   {'*','0','#'}};
      
      	//Base Case
    	if(n <= 0) 
    		return 0; 
    	if(n == 1) 
    		return 10; 
    
    	//Directions to move to
    	int dir[][]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};
    
    	//dp[i][j] = number of sequences of length j starting with digit i
    	int dp[][] = new int[10][n+1];
        
        for(int i=0;i<10;i++)
            for(int j=0;j<n+1;j++)
                dp[i][j]= 0;
                
    	// fill the numbers starting with digit i and of length 1 
    	for(int i=0; i<=9; i++)
    		dp[i][1] = 1;
    
    	// Now solve problem for n=2,3,.. using smaller sub-problems
    	for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
    	{ 
    		for(int row=0; row<4; row++)
    		{ 
    			for (int col=0; col<3; col++)
    			{ 
    				if (keypad[row][col] != '*' && keypad[row][col] != '#') 
    				{ 
    					//fixing the first digit
    					int num = keypad[row][col] - '0';
    
    					//Now select the remaining digit in sequence
    					for(int step=0; step<5; step++) 
    					{ 
    						int new_row = row + dir[step][0]; 
    						int new_col = col + dir[step][1]; 
    						if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
                                                && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
    						{ 
    							int nextNum = keypad[new_row][new_col] - '0'; 
    							dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
    						} 
    					} 
    				} 
    			} 
    		} 
    	} 
    
      	// Add the number of sequences of length starting with digit i(0 to 9)
    	int ans = 0; 
    	for(int i=0; i<=9; i++) 
    		ans += dp[i][n]; 
    	return ans; 
    } 

    public static void main(String[] args) 
    { 
        
    	Scanner sc = new Scanner(System.in); 
    	int t = sc.nextInt(); 
    	while(t-- > 0){ 
            int n = sc.nextInt();
            int ans = findNumberOfSequences(n);
    	    System.out.println("Number of sequences of length "+n+" = "+ans);
    	}
    } 
}
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36
Number of sequences of length 3 = 138
Number of sequences of length 4 = 532
Number of sequences of length 5 = 2062

Анализ на сложността

Сложност във времето: O (n) за проблем с мобилна цифрова клавиатура

Въпреки че сме използвали много вложени цикли, но и след това ги считаме да работят в постоянно време, като по този начин имаме линейна времева сложност O (n) само заради външния цикъл.

Сложност на пространството: O (n) за проблем с мобилна цифрова клавиатура

Тъй като имаме едномерен DP масив с размер n. Имаме линейна пространствена сложност на O (n).