O(n) time O(n) space can be reduced to O(1) space Java solution


  • 0
    D
    public class Solution {
        public int numWays(int n, int k) {
            if (n < 1) return 0;
            if (n == 1) return k;
            /* _1_map means this node has k choices;
             * _2_map means this node has k - 1 choices;
             * _3_map means this node has 1 choice.
             * can be reduced to 3 integers.
             */
            int[] _1_map = new int[n + 1], _2_map = new int[n + 1], _3_map = new int[n + 1];
            for (int i = n; i >= 1; i--) {
                for (int j = 1; j <= 3; j++) {
                    if (i == n) {
                        switch (j) {
                            case 1: _1_map[i] = k; break;
                            case 2: _2_map[i] = k - 1; break;
                            case 3: _3_map[i] = 1; break;
                        }
                        continue;
                    }
                    switch (j) {
                        case 1: _1_map[i] = k * (_3_map[i + 1] + _2_map[i + 1]); break;
                        case 2: _2_map[i] = (k - 1) * (_3_map[i + 1] + _2_map[i + 1]); break;
                        case 3: _3_map[i] = _2_map[i + 1]; break;
                    }
                }
            }
            return _1_map[1];
        }
    }

Log in to reply
 

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