# Simple Java dp solution for with O(n) time and space, can be reduced to O(1) space

• ``````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[i-1]*(k-1) + dp[i-2]*(k-1);
}
}
return dp[n-1];
}
}``````

• You can use int[] dp = new int[3] to make it in place.

• 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 * (k-1);

for(int i = 2; i < n; i++){
int temp = sameColor;
sameColor = notSame;
notSame = temp * (k-1) + notSame * (k-1);
}

return sameColor + notSame;
}``````

• Smart solution!!!

• The second line is redundant, and the third line and first line have overlap interval. I think you should change it to:

``````if(n == 0) return 0;
else if(n == 1) return k;``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.