Sharing my C++ DP solution


  • 0
    T
    class Solution {
    public:
        int numWays(int n, int k) {
            if(n==0)
                return 0;
            if(n==1)
                return k;
            vector<int> DPsame(n, 0);
            vector<int> DPdifferent(n, 0);
            DPsame[1] = k;
            DPdifferent[1] = k*(k-1);
            for(int i=2; i<n; i++)
            {
                DPsame[i] = DPdifferent[i-1];
                DPdifferent[i] = (DPdifferent[i-1]+DPsame[i-1])*(k-1);
            }
            
            return DPsame[n-1]+DPdifferent[n-1];
        }
    };

  • 0
    N
    This post is deleted!

Log in to reply
 

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