Dynamic programming with O(n) time complexity


  • 1
    R
    public class Solution {
    	public int numWays(int n, int k) {
    		if (n == 0) {
    			return 0;
    		}
    		if (n > 2 && k <= 1) {
    			return 0;
    		}
    		int[][] p = new int[n][2];
    
    		/*
    		* p[x][0] means p[x] and p[x-1] have different color p[x][1] means
    		* p[x] and p[x-1] have the same color
    		*/
    
    		// At the first position, there is no post before, its color can be any color
    		p[0][0] = k; 
    		p[0][1] = 0;
    		for (int i = 1; i < n; i++) {
    			// if p[x] wanted to be painted the same color as the previous post, there is only one choice
    			p[i][1] = p[i - 1][0] * 1;
    			// if p[x] wanted to be painted different color from previous post, there are k-1 choices. 
    			// And there are two kinds of p[x-1] situation: same or different with previous post
    			p[i][0] = (p[i - 1][1] + p[i - 1][0]) * (k - 1);
    		}
    
    		return p[n - 1][0] + p[n - 1][1];
    	}
    }
    

Log in to reply
 

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