My C++ DP solution - O(n) Time and O(1) Space - Short and Easy!!!


  • 0
    E
    class Solution {
    public:
        int numWays(int n, int k) {
            if(n == 0 || k == 0) {
                return 0;
            }
            if(n == 1) {
                return k;
            }
            int prev = 1; 
            int cur = k;
            for(int i = 2 ; i < n ; ++i) {
                int tmp = (k - 1) * (prev + cur);
                prev = cur;
                cur = tmp;
            }
            return k * cur;
        }
    };

Log in to reply
 

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