Dado n, encuentra el conteo de n dígitos Números escalonados. Un número se llama número de paso si todos los dígitos adyacentes tienen una diferencia absoluta de 1. 321 es un número de paso mientras que 421 no lo es.
Ejemplos:
Input : 2 Output : 17 The numbers are 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98. Input : 1 Output : 10 The numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
En la publicación anterior , se analiza una solución que requiere espacio auxiliar O(n). Se puede optimizar el espacio auxiliar necesario para resolver el problema. La array bidimensional dp dp[i][j] representa el número de pasos de longitud i y el último dígito j. Para un dígito j el conteo se obtiene del dígito j – 1 y j + 1. La relación de recurrencia es dp[i][j] = dp[i-1][j-1] + dp[i-1][j +1] . Observe que la respuesta para la longitud actual i depende solo de i – 1. Por lo tanto, se puede usar una array dp 1-D en la que para una i dada, dp[j] almacena el recuento de números escalonados de longitud i que terminan con el dígito j. Antes de actualizar el arreglo dp para una longitud dada i, almacene el resultado para el largo i – 1 en otro arreglo anterior , luego actualice el arreglo dp usando el arreglo anterior .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to calculate the number of
// n digit stepping numbers.
#include <bits/stdc++.h>
using namespace std;
// function that calculates the answer
long long answer(int n)
{
// dp[j] stores count of i digit
// stepping numbers ending with digit
// j.
int dp[10];
// To store result of length i - 1
// before updating dp[j] for length i.
int prev[10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[j] = 1;
// Compute values for count of digits
// more than 1.
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
prev[j] = dp[j];
}
for (int j = 0; j <= 9; j++) {
// If ending digit is 0
if (j == 0)
dp[j] = prev[j + 1];
// If ending digit is 9
else if (j == 9)
dp[j] = prev[j - 1];
// For other digits.
else
dp[j] = prev[j - 1] + prev[j + 1];
}
}
// stores the final answer
long long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[j];
return sum;
}
// driver program to test the above function
int main()
{
int n = 2;
cout << answer(n);
return 0;
}
Java
// Java program to calculate the number of
// n digit stepping numbers.
class GFG
{
// function that calculates the answer
static long answer(int n)
{
// dp[j] stores count of i digit
// stepping numbers ending with digit
// j.
int[] dp = new int[10];
// To store result of length i - 1
// before updating dp[j] for length i.
int[] prev = new int[10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[j] = 1;
// Compute values for count of digits
// more than 1.
for (int i = 2; i <= n; i++)
{
for (int j = 0; j <= 9; j++)
{
prev[j] = dp[j];
}
for (int j = 0; j <= 9; j++)
{
// If ending digit is 0
if (j == 0)
dp[j] = prev[j + 1];
// If ending digit is 9
else if (j == 9)
dp[j] = prev[j - 1];
// For other digits.
else
dp[j] = prev[j - 1] + prev[j + 1];
}
}
// stores the final answer
long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[j];
return sum;
}
// Driver code
public static void main (String[] args)
{
int n = 2;
System.out.println(answer(n));
}
}
// This code is contributed by mits
Python3
# Python3 program to calculate the number of # n digit stepping numbers. # function that calculates the answer def answer(n) : # dp[j] stores count of i digit # stepping numbers ending with digit j. dp = [0] * 10 # To store resu1lt of length i - 1 # before updating dp[j] for length i. prev = [0] * 10 # if n is 1 then answer will be 10. if (n == 1): return 10 # Initialize values for count of # digits equal to 1. for j in range(0, 10) : dp[j] = 1 # Compute values for count of digits # more than 1. for i in range(2, n + 1): for j in range (0, 10): prev[j] = dp[j] for j in range (0, 10): # If ending digit is 0 if (j == 0): dp[j] = prev[j + 1] # If ending digit is 9 elif (j == 9) : dp[j] = prev[j - 1] # For other digits. else : dp[j] = prev[j - 1] + prev[j + 1] # stores the final answer sum = 0 for j in range (1, 10): sum = sum + dp[j] return sum # Driver Code n = 2 print(answer(n)) # This code is contributed by ihritik
C#
// C# program to calculate the number of
// n digit stepping numbers.
using System;
class GFG
{
// function that calculates the answer
static long answer(int n)
{
// dp[j] stores count of i digit
// stepping numbers ending with digit
// j.
int[] dp = new int[10];
// To store result of length i - 1
// before updating dp[j] for length i.
int[] prev = new int[10];
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (int j = 0; j <= 9; j++)
dp[j] = 1;
// Compute values for count of digits
// more than 1.
for (int i = 2; i <= n; i++)
{
for (int j = 0; j <= 9; j++)
{
prev[j] = dp[j];
}
for (int j = 0; j <= 9; j++)
{
// If ending digit is 0
if (j == 0)
dp[j] = prev[j + 1];
// If ending digit is 9
else if (j == 9)
dp[j] = prev[j - 1];
// For other digits.
else
dp[j] = prev[j - 1] + prev[j + 1];
}
}
// stores the final answer
long sum = 0;
for (int j = 1; j <= 9; j++)
sum += dp[j];
return sum;
}
// Driver code
static void Main()
{
int n = 2;
Console.WriteLine(answer(n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to calculate the number of
// n digit stepping numbers.
// function that calculates the answer
function answer($n)
{
// dp[j] stores count of i digit
// stepping numbers ending with digit
// j.
$dp = array_fill(0, 10, 0);
// To store result of length i - 1
// before updating dp[j] for length i.
$prev = array_fill(0, 10, 0);;
// if n is 1 then answer will be 10.
if ($n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for ($j = 0; $j <= 9; $j++)
$dp[$j] = 1;
// Compute values for count of digits
// more than 1.
for ($i = 2; $i <= $n; $i++)
{
for ($j = 0; $j <= 9; $j++)
{
$prev[$j] = $dp[$j];
}
for ($j = 0; $j <= 9; $j++)
{
// If ending digit is 0
if ($j == 0)
$dp[$j] = $prev[$j + 1];
// If ending digit is 9
else if ($j == 9)
$dp[$j] = $prev[$j - 1];
// For other digits.
else
$dp[$j] = $prev[$j - 1] + $prev[$j + 1];
}
}
// stores the final answer
$sum = 0;
for ($j = 1; $j <= 9; $j++)
$sum += $dp[$j];
return $sum;
}
// Driver program to test the above function
$n = 2;
echo answer($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to calculate the number of
// n digit stepping numbers.
// function that calculates the answer
function answer(n)
{
// dp[j] stores count of i digit
// stepping numbers ending with digit
// j.
var dp = Array(10);
// To store result of length i - 1
// before updating dp[j] for length i.
var prev = Array(10);
// if n is 1 then answer will be 10.
if (n == 1)
return 10;
// Initialize values for count of
// digits equal to 1.
for (var j = 0; j <= 9; j++)
dp[j] = 1;
// Compute values for count of digits
// more than 1.
for (var i = 2; i <= n; i++) {
for (var j = 0; j <= 9; j++) {
prev[j] = dp[j];
}
for (var j = 0; j <= 9; j++) {
// If ending digit is 0
if (j == 0)
dp[j] = prev[j + 1];
// If ending digit is 9
else if (j == 9)
dp[j] = prev[j - 1];
// For other digits.
else
dp[j] = prev[j - 1] + prev[j + 1];
}
}
// stores the final answer
var sum = 0;
for (var j = 1; j <= 9; j++)
sum += dp[j];
return sum;
}
// driver program to test the above function
var n = 2;
document.write( answer(n));
</script>
Producción:
17
Complejidad Temporal: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.