Colorea N cuadros usando M colores de manera que K cuadros tengan un color diferente al cuadro de su izquierda

Dado N número de casillas dispuestas en fila y M número de colores. La tarea es encontrar el número de formas de pintar esas N cajas usando M colores de manera que haya exactamente K cajas con un color diferente al color de la caja a su izquierda. Imprime esta respuesta modulo 998244353 .
Ejemplos: 
 

Entrada: N = 3, M = 3, K = 0 
Salida: 3 
Dado que el valor de K es cero, ningún cuadro puede tener un color diferente del color del cuadro a su izquierda. Por lo tanto, todas las cajas deben pintarse con el mismo color y dado que hay 3 tipos de colores, hay un total de 3 formas. 
Entrada: N = 3, M = 2, K = 1 
Salida: 4 
Numeremos los colores como 1 y 2. Cuatro secuencias posibles de pintar 3 cajas con 1 caja que tiene un color diferente al color de la caja a su izquierda son (1 2 2 ), (1 1 2), (2 1 1) (2 2 1) 
 

Requisitos previos: programación dinámica
 

Enfoque: este problema se puede resolver usando programación dinámica donde dp[i][j] denotará el número de formas de pintar i cajas usando M colores de manera que haya exactamente j cajas con un color diferente al color de la caja en su izquierda. Para cada cuadro actual excepto 1 ^st , podemos pintar el mismo color que pintó en su cuadro izquierdo y resolver para dp[i – 1][j] o podemos pintarlo con el color M – 1 restante y resolver para dp[i – 1][j – 1] recursivamente.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP Program to Paint N boxes using M
// colors such that K boxes have color
// different from color of box on its left
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 998244353;
 
vector<vector<int>> dp;
 
// This function returns the required number
// of ways where idx is the current index and
// diff is number of boxes having different
// color from box on its left
int solve(int idx, int diff, int N, int M, int K)
{
    // Base Case
    if (idx > N) {
        if (diff == K)
            return 1;
        return 0;
    }
 
    // If already computed
    if (dp[idx][ diff] != -1)
        return dp[idx][ diff];
 
    // Either paint with same color as
    // previous one
    int ans = solve(idx + 1, diff, N, M, K);
 
    // Or paint with remaining (M - 1)
    // colors
    ans = ans % MOD + ((M - 1) % MOD * solve(idx + 1, diff + 1, N, M, K) % MOD) % MOD;
 
    return dp[idx][ diff] = ans;
}
 
// Driver code
int main()
{
    int N = 3, M = 3, K = 0;
    dp = vector<vector<int>>(N+1,vector<int>(N+1,-1));
 
    // Multiply M since first box can be
    // painted with any of the M colors and
    // start solving from 2nd box
    cout << (M * solve(2, 0, N, M, K)) << endl;
 
    return 0;
}

// Java Program to Paint N boxes using M
// colors such that K boxes have color
// different from color of box on its left
 
class GFG
{
     
    static int M = 1001;
    static int MOD = 998244353;
 
    static int[][] dp = new int[M][M];
 
    // This function returns the required number
    // of ways where idx is the current index and
    // diff is number of boxes having different
    // color from box on its left
    static int solve(int idx, int diff,
                        int N, int M, int K)
    {
        // Base Case
        if (idx > N)
        {
            if (diff == K)
                return 1;
            return 0;
        }
 
        // If already computed
        if (dp[idx][ diff] != -1)
            return dp[idx][ diff];
 
        // Either paint with same color as
        // previous one
        int ans = solve(idx + 1, diff, N, M, K);
 
        // Or paint with remaining (M - 1)
        // colors
        ans += (M - 1) * solve(idx + 1,
                diff + 1, N, M, K);
 
        return dp[idx][ diff] = ans % MOD;
    }
 
    // Driver code
    public static void main (String[] args)
    {
        int N = 3, M = 3, K = 0;
        for(int i = 0; i <= M; i++)
            for(int j = 0; j <= M; j++)
                dp[i][j] = -1;
     
        // Multiply M since first box can be
        // painted with any of the M colors and
        // start solving from 2nd box
        System.out.println((M * solve(2, 0, N, M, K)));
    }
}
 
// This code is contributed by mits

# Python3 Program to Paint N boxes using M
# colors such that K boxes have color
# different from color of box on its left
 
M = 1001;
MOD = 998244353;
 
dp = [[-1]* M ] * M
 
# This function returns the required number
# of ways where idx is the current index and
# diff is number of boxes having different
# color from box on its left
def solve(idx, diff, N, M, K) :
     
    # Base Case
    if (idx > N) :
        if (diff == K) :
            return 1
        return 0
 
    # If already computed
    if (dp[idx][ diff] != -1) :
        return dp[idx];
 
    # Either paint with same color as
    # previous one
    ans = solve(idx + 1, diff, N, M, K);
 
    # Or paint with remaining (M - 1)
    # colors
    ans += (M - 1) * solve(idx + 1, diff + 1, N, M, K);
 
    dp[idx][ diff] = ans % MOD;
     
    return dp[idx][ diff]
 
# Driver code
if __name__ == "__main__" :
 
    N = 3
    M = 3
    K = 0
 
    # Multiply M since first box can be
    # painted with any of the M colors and
    # start solving from 2nd box
    print(M * solve(2, 0, N, M, K))
 
# This code is contributed by Ryuga

// C# Program to Paint N boxes using M
// colors such that K boxes have color
// different from color of box on its left
using System;
class GFG
{
     
static int M = 1001;
static int MOD = 998244353;
 
static int[,] dp = new int[M, M];
 
// This function returns the required number
// of ways where idx is the current index and
// diff is number of boxes having different
// color from box on its left
static int solve(int idx, int diff,
                 int N, int M, int K)
{
    // Base Case
    if (idx > N)
    {
        if (diff == K)
            return 1;
        return 0;
    }
 
    // If already computed
    if (dp[idx, diff] != -1)
        return dp[idx, diff];
 
    // Either paint with same color as
    // previous one
    int ans = solve(idx + 1, diff, N, M, K);
 
    // Or paint with remaining (M - 1)
    // colors
    ans += (M - 1) * solve(idx + 1,
                diff + 1, N, M, K);
 
    return dp[idx, diff] = ans % MOD;
}
 
// Driver code
public static void Main ()
{
    int N = 3, M = 3, K = 0;
    for(int i = 0; i <= M; i++)
        for(int j = 0; j <= M; j++)
            dp[i, j] = -1;
 
    // Multiply M since first box can be
    // painted with any of the M colors and
    // start solving from 2nd box
    Console.WriteLine((M * solve(2, 0, N, M, K)));
}
}
 
// This code is contributed by chandan_jnu

<?php
// PHP Program to Paint N boxes using M
// colors such that K boxes have color
// different from color of box on its left
 
$M = 1001;
$MOD = 998244353;
 
$dp = array_fill(0, $M,
      array_fill(0, $M, -1));
 
// This function returns the required number
// of ways where idx is the current index
// and diff is number of boxes having
// different color from box on its left
function solve($idx, $diff, $N, $M, $K)
{
    global $dp, $MOD;
     
    // Base Case
    if ($idx > $N)
    {
        if ($diff == $K)
            return 1;
        return 0;
    }
 
    // If already computed
    if ($dp[$idx][$diff] != -1)
        return $dp[$idx][$diff];
 
    // Either paint with same color
    // as previous one
    $ans = solve($idx + 1, $diff, $N, $M, $K);
 
    // Or paint with remaining (M - 1)
    // colors
    $ans += ($M - 1) * solve($idx + 1,
             $diff + 1, $N, $M, $K);
 
    return $dp[$idx][$diff] = $ans % $MOD;
}
 
// Driver code
$N = 3;
$M = 3;
$K = 0;
 
// Multiply M since first box can be
// painted with any of the M colors and
// start solving from 2nd box
echo ($M * solve(2, 0, $N, $M, $K));
 
// This code is contributed by chandan_jnu
?>

<script>
 
    // JavaScript Program to Paint N boxes using M
    // colors such that K boxes have color
    // different from color of box on its left
     
    let m = 1001;
    let MOD = 998244353;
   
    let dp = new Array(m);
    for(let i = 0; i < m; i++)
    {
        dp[i] = new Array(m);
        for(let j = 0; j < m; j++)
        {
            dp[i][j] = 0;
        }
    }
   
    // This function returns the required number
    // of ways where idx is the current index and
    // diff is number of boxes having different
    // color from box on its left
    function solve(idx, diff, N, M, K)
    {
        // Base Case
        if (idx > N)
        {
            if (diff == K)
                return 1;
            return 0;
        }
   
        // If already computed
        if (dp[idx][ diff] != -1)
            return dp[idx][ diff];
   
        // Either paint with same color as
        // previous one
        let ans = solve(idx + 1, diff, N, M, K);
   
        // Or paint with remaining (M - 1)
        // colors
        ans += (M - 1) * solve(idx + 1,
                diff + 1, N, M, K);
          dp[idx][ diff] = ans % MOD;
        return dp[idx][ diff];
    }
     
    let N = 3, M = 3, K = 0;
    for(let i = 0; i <= M; i++)
      for(let j = 0; j <= M; j++)
        dp[i][j] = -1;
 
    // Multiply M since first box can be
    // painted with any of the M colors and
    // start solving from 2nd box
    document.write((M * solve(2, 0, N, M, K)));
     
</script>

3

Complejidad temporal: O(M*M)
Espacio auxiliar: O(M*M)