public class Solution {
public int numWays(int n, int k) {
if(n == 0  k == 0) return 0;
int[] dp = new int[n];
for(int i = 0; i < n; i++){
if(i == 0){
dp[i] = k;
}
else if(i == 1){
dp[i] = k*k;
}
else{
dp[i] = dp[i1]*(k1) + dp[i2]*(k1);
}
}
return dp[n1];
}
}
Simple Java dp solution for with O(n) time and space, can be reduced to O(1) space

Similar idea here
public int numWays(int n, int k) { if(n == 0) return 0; if(n ==2) return k * k; if(n <= 1) return k; int sameColor = k; int notSame = k * (k1); for(int i = 2; i < n; i++){ int temp = sameColor; sameColor = notSame; notSame = temp * (k1) + notSame * (k1); } return sameColor + notSame; }