public int numWays(int n, int k) {

if (k == 0 || n == 0) return 0;

int[][] dp = new int[n][2];

dp[0][0] = k;

dp[0][1] = 0;

for (int i=1; i<n; i++) {

dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k - 1);

dp[i][1] = dp[i-1][0];

}

return dp[n-1][0] + dp[n-1][1];

}

public int numWays2(int n, int k) {

if (k == 0 || n == 0) return 0;

int diff = k;

int same = 0;

for (int i=1; i<n; i++) {

int s = same;

int d = diff;

diff = (s + d) * (k - 1);

same = d;

}

return same + diff;

}