Java O(n) Time, O(1) Space


  • 0
    V
    public class Solution {
        public int numWays(int n, int k) {
            if (n <= 1) return n * k;
            
            int w1 = k, w0 = 1;
            for (int i = 3; i <= n; i++) {
                int w2 = (k - 1) * (w1 + w0);
                w0 = w1;
                w1 = w2;
            }
            
            return k * w1;
        }
    }
    

Log in to reply
 

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