Recuento de números de N dígitos con diferencia absoluta de dígitos adyacentes que no exceda K

Dados dos números enteros N y K , la tarea es encontrar el conteo de números de N dígitos tal que la diferencia absoluta de los dígitos adyacentes en el número no sea mayor que K .

Ejemplos: 

Entrada: N = 2, K = 1 
Salida: 26 
Explicación: Los números son 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66 , 67, 76, 77, 78, 87, 88, 89, 98, 99

Entrada: N = 3, K = 2 
Salida: 188 
 

Enfoque ingenuo 
El enfoque más simple es iterar sobre todos los números de N dígitos y verificar para cada número si los dígitos adyacentes tienen una diferencia absoluta menor o igual a K. 
Complejidad de tiempo: O (10 ^N * N)

Enfoque eficiente: 
para optimizar el enfoque anterior, necesitamos usar un enfoque de programación dinámica junto con actualización de rango 

• Inicialice una array DP[][] donde dp[i][j] almacena el recuento de números que tienen i dígitos y terminan en j .
• Repita la array de 2 a N y verifique si el último dígito fue j, entonces los dígitos permitidos para este lugar están en el rango (max(0, jk), min(9, j+k)) . Realice una actualización de rango en este rango.
• Ahora use Prefix Sum para obtener la respuesta real.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
long long getCount(int n, int k)
{
    // For 1-digit numbers,
    // the count is 10
    if (n == 1)
        return 10;
 
    long long dp[n + 1][11];
 
    // dp[i][j] stores the number
    // of such i-digit numbers
    // ending in j
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 11; j++)
            dp[i][j] = 0;
    }
    // Initialize count for
    // 1-digit numbers
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    // Compute values for count of
    // digits greater than 1
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
 
            // Find the range of allowed
            // numbers if last digit is j
            int l = max(0, j - k);
            int r = min(9, j + k);
 
            // Perform Range update
            dp[i][l] += dp[i - 1][j];
            dp[i][r + 1] -= dp[i - 1][j];
        }
 
        // Prefix sum to find actual
        // values of i-digit numbers
        // ending in j
        for (int j = 1; j <= 9; j++)
            dp[i][j] += dp[i][j - 1];
    }
 
    // Stores the final answer
    long long count = 0;
    for (int i = 0; i <= 9; i++)
        count += dp[n][i];
 
    return count;
}
 
// Driver Code
int main()
{
    int N = 2, K = 1;
    cout << getCount(N, K);
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG {
 
    // Function to return count of such numbers
    public static long getCount(int n, int k)
    {
        // For 1-digit numbers, the count
        // is 10 irrespective of K
        if (n == 1)
            return 10;
 
        // dp[i][j] stores the number
        // of such i-digit numbers
        // ending in j
        long dp[][]
            = new long[n + 1][11];
 
        // Initialize count for
        // 1-digit numbers
        for (int i = 1; i <= 9; i++)
            dp[1][i] = 1;
 
        // Compute values for count of
        // digits greater than 1
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
 
                // Find the range of allowed
                // numbers if last digit is j
                int l = Math.max(0, j - k);
                int r = Math.min(9, j + k);
 
                // Perform Range update
                dp[i][l] += dp[i - 1][j];
                dp[i][r + 1] -= dp[i - 1][j];
            }
 
            // Prefix sum to find actual values
            // of i-digit numbers ending in j
            for (int j = 1; j <= 9; j++)
                dp[i][j] += dp[i][j - 1];
        }
 
        // Stores the final answer
        long count = 0;
        for (int i = 0; i <= 9; i++)
            count += dp[n][i];
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 2, k = 1;
        System.out.println(getCount(n, k));
    }
}

# Python 3 Program to implement
# the above approach
 
# Function to return count
# of N-digit numbers with
# absolute difference of
# adjacent digits not
# exceeding K
def getCount(n, k):
 
    # For 1-digit numbers, the
    # count is 10
    if n == 1:
        return 10
     
    # dp[i][j] stores the count of
    # i-digit numbers ending with j       
    dp = [[0 for x in range(11)]
            for y in range(n + 1)];    
     
     
    # Initialize count for
    # 1-digit numbers
    for i in range(1, 10):
        dp[1][i]= 1
     
    # Compute values for count
    # of digits greater than 1
    for i in range(2, n + 1):
        for j in range(0, 10):
             
            # Find the range of allowed
            # numbers if last digit is j
            l = max(0, j - k)
            r = min(9, j + k)
                 
            # Perform Range update
            dp[i][l] = dp[i][l] + dp[i-1][j]
            dp[i][r + 1] = dp[i][r + 1] - dp[i-1][j]
             
        # Prefix sum to find count of
        # of i-digit numbers ending with j
        for j in range(1, 10):
            dp[i][j] = dp[i][j] + dp[i][j-1]
     
    # Stores the final answer
    count = 0
     
    for i in range(0, 10):
        count = count + dp[n][i]
    return count
 
# Driver Code
n, k = 2, 1
print(getCount(n, k))

// C# Program to implement
// the above approach
using System;
class GFG {
 
    // Function to return the
    // count of N-digit numbers
    // with absolute difference of
    // adjacent digits not exceeding K
    static long getCount(int n, int k)
    {
        // For 1-digit numbers, the
        // count is 10
        if (n == 1)
            return 10;
 
        // dp[i][j] stores the count of
        // i-digit numbers ending with j
        long[, ] dp = new long[n + 1, 11];
 
        // Initialize count for
        // 1-digit numbers
        for (int i = 1; i <= 9; i++)
            dp[1, i] = 1;
 
        // Compute values for count of
        // digits greater than 1
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
 
                // Find the range of allowed
                // numbers with last digit j
                int l = Math.Max(0, j - k);
                int r = Math.Min(9, j + k);
 
                // Perform Range update
                dp[i, l] += dp[i - 1, j];
                dp[i, r + 1] -= dp[i - 1, j];
            }
 
            // Prefix sum to count i-digit
            // numbers ending in j
            for (int j = 1; j <= 9; j++)
                dp[i, j] += dp[i, j - 1];
        }
 
        // Stores the final answer
        long count = 0;
        for (int i = 0; i <= 9; i++)
            count += dp[n, i];
        return count;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 2, k = 1;
        Console.WriteLine(getCount(n, k));
    }
}

<script>
 
// Javascript implementation of
// the above approach
 
// Function to return count
// of N-digit numbers with
// absolute difference of
// adjacent digits not
// exceeding K
function getCount(n, k)
{
     
    // For 1-digit numbers, the count
    // is 10 irrespective of K
    if (n == 1)
        return 10;
 
    // dp[i][j] stores the number
    // of such i-digit numbers
    // ending in j
    var dp = new Array(n + 1);
    for(var i = 0; i < dp.length; i++)
        dp[i] = Array(11).fill(0);
 
    // Initialize count for
    // 1-digit numbers
    for(i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    // Compute values for count of
    // digits greater than 1
    for(i = 2; i <= n; i++)
    {
        for(j = 0; j <= 9; j++)
        {
             
            // Find the range of allowed
            // numbers if last digit is j
            var l = Math.max(0, j - k);
            var r = Math.min(9, j + k);
 
            // Perform Range update
            dp[i][l] += dp[i - 1][j];
            dp[i][r + 1] -= dp[i - 1][j];
        }
 
        // Prefix sum to find actual values
        // of i-digit numbers ending in j
        for(j = 1; j <= 9; j++)
            dp[i][j] += dp[i][j - 1];
    }
 
    // Stores the final answer
    var count = 0;
    for(i = 0; i <= 9; i++)
        count += dp[n][i];
         
    return count;
}
 
// Driver Code
var n = 2, k = 1;
 
document.write(getCount(n, k));
 
// This code is contributed by umadevi9616
 
</script>

26

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)