LeetCode – Pain Fence (Java)

Hay una cerca con n postes, cada poste se puede pintar con uno de los k colores. Debe pintar todos los postes de manera que no más de dos postes de cerca adyacentes tengan el mismo color. Devuelve el número total de formas en que puedes pintar la cerca.

Solución Java

La clave para resolver este problema es encontrar esta relación.

f (n) = (k-1) (f (n-1) + f (n-2))

Suponiendo que hay 3 publicaciones, si la primera y la segunda tienen el mismo color, la tercera tiene opciones k-1. El primero y el segundo juntos tienen k opciones.
Si el primero y el segundo no tienen el mismo color, el total es k * (k-1), entonces el tercero tiene k opciones. Por lo tanto, f (3) = (k-1) * k + k * (k-1) * k = (k-1) (k + k * k)

public int numWays(int n, int k) {
    int dp[] = {0, k , k*k, 0};
 
    if(n <= 2)
        return dp[n];
 
    for(int i = 2; i < n; i++){
        dp[3] = (k - 1) * (dp[1] + dp[2]);
        dp[1] = dp[2];
        dp[2] = dp[3];
    }
 
    return dp[3];
}