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


  • 14
    J
    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];
        }
    }

  • 0

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


  • 1
    H

    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;
    }

  • 0
    Y

    Smart solution!!!


  • 0

    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;

Log in to reply
 

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