Праблема мабільнай лічбавай клавіятуры


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка MAQ Microsoft Спрынклер
Камбінаторыя Дынамічнае праграмаванне матрыца Радок

Пастаноўка праблемы

У праблеме мабільнай лічбавай клавіятуры мы разглядаем лічбавую клавіятуру. Нам трэба знайсці ўсю колькасць магчымых лікавых паслядоўнасцей дадзенай даўжыні, каб вам было дазволена націскаць толькі кнопкі зверху, уніз, злева і справа ад бягучай кнопкі. Вам не дазволена націскаць кутнія кнопкі ніжняга радка (* (зорка) і # (хэш)), якія пазначаны шэрым на малюнку ніжэй.

Лікавая клавіятура

Прыклад

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) з нумарамі нумароў 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).