Module Expr Str Assign NameStore Str ClassDef bases NameLoad body FunctionDef arguments args NameParam NameParam NameParam defaults body Return IfExp CompareLt NameLoad Num Num Call NameLoad Call NameLoad Lambda arguments args NameParam NameParam defaults ListLoad BinOpMult BinOpSub NameLoad Num BinOpAdd SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index Num Call NameLoad Num NameLoad ListLoad NameLoad Num decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str If CompareLt NameLoad Num body Return Num Assign NameStore NameLoad Assign NameStore Num For NameStore Call NameLoad Num NameLoad body Assign TupleStore NameStore NameStore TupleLoad BinOpMult BinOpSub NameLoad Num BinOpAdd NameLoad NameLoad NameLoad Return BinOpAdd NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str If CompareLt NameLoad Num body Return Num Assign NameStore ListComp ListComp ListComp Num comprehension NameStore Call NameLoad NameLoad comprehension NameStore Call NameLoad NameLoad comprehension NameStore Call NameLoad Num Assign NameStore Num For NameStore Call NameLoad NameLoad body Assign SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index Num Index NameLoad Index NameLoad Num For NameStore Call NameLoad Num BinOpAdd NameLoad Num body For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body Assign SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index BinOpMod NameLoad Num Index NameLoad Index NameLoad Num For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body If CompareEq NameLoad Num body Assign SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index BinOpMod NameLoad Num Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpMod BinOpSub NameLoad Num Num Index NameLoad Index NameLoad orelse If BoolOpAnd CompareEq NameLoad NameLoad CompareNotEq NameLoad NameLoad body AugAssignAdd SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index BinOpMod NameLoad Num Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpMod BinOpSub NameLoad Num Num Index NameLoad Index NameLoad orelse If CompareNotEq NameLoad NameLoad body AugAssignAdd SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index BinOpMod NameLoad Num Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpMod BinOpSub NameLoad Num Num Index NameLoad Index NameLoad Assign NameStore Num For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body AugAssignAdd NameStore SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpMod NameLoad Num Index NameLoad Index NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str If CompareLt NameLoad Num body Return Num Assign NameStore ListComp ListComp ListComp Num comprehension NameStore Call NameLoad NameLoad comprehension NameStore Call NameLoad NameLoad comprehension NameStore Call NameLoad BinOpAdd NameLoad Num Assign NameStore Num For NameStore Call NameLoad NameLoad body Assign SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index Num Index NameLoad Index NameLoad Num For NameStore Call NameLoad Num BinOpAdd NameLoad Num body For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body If CompareEq NameLoad Num body Assign SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpSub NameLoad Num Index NameLoad Index NameLoad orelse If BoolOpAnd CompareEq NameLoad NameLoad CompareNotEq NameLoad NameLoad body AugAssignAdd SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpSub NameLoad Num Index NameLoad Index NameLoad orelse If CompareNotEq NameLoad NameLoad body AugAssignAdd SubscriptStore SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index NameLoad SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index BinOpSub NameLoad Num Index NameLoad Index NameLoad Assign NameStore Num For NameStore Call NameLoad NameLoad body For NameStore Call NameLoad NameLoad body AugAssignAdd NameStore SubscriptLoad SubscriptLoad SubscriptLoad NameLoad Index NameLoad Index NameLoad Index NameLoad Return NameLoad decorator_list decorator_list If CompareEq NameLoad Str body Assert CompareEq Call AttributeLoad Call NameLoad attr Num Num Num
N/A N/A 
Premium Question
 N/A __author__ Daniel Solution N/A object N/A numWays_oneliner N/A N/A self n k N/A N/A N/A N/A N/A n 1 0 N/A sum N/A reduce N/A N/A N/A F i N/A N/A N/A N/A k 1 N/A N/A F N/A 0 N/A F N/A 1 N/A F N/A 0 N/A xrange 1 n N/A k 0 N/A numWays N/A N/A self n k N/A N/A N/A 
        You need to abstract number of colors to binary value (is different color)

        Let F1[i] be the number of ways for A[:i] with last two with different colors
            F2[i] be the number of ways for A[:i] with last two with same color

        F1[i] = (k-1)*(F1[i-1]+F2[i-1])
        F2[i] = F1[i-1]

        Optimize the space since only depends on i and i-1

        :type n: int
        :type k: int
        :rtype: int
         N/A N/A n 1 N/A N/A 0 N/A num_diff k N/A num_same 0 N/A _ N/A xrange 1 n N/A N/A N/A num_diff num_same N/A N/A N/A k 1 N/A num_diff num_same num_diff N/A N/A num_diff num_same N/A numWays_MLE2 N/A N/A self n k N/A N/A N/A 
        DP
        Let F[i][j][l] be the number of ways of painting for A[:i] with A[i-1] as color j and A[i-2] as color l
        :type n: int
        :type k: int
        :rtype: int
         N/A N/A n 1 N/A N/A 0 N/A F N/A N/A N/A 0 N/A _ N/A xrange k N/A _ N/A xrange k N/A _ N/A xrange 2 N/A EMPTY 0 N/A j0 N/A xrange k N/A N/A N/A N/A N/A F N/A 1 N/A j0 N/A EMPTY 1 N/A i N/A xrange 2 N/A n 1 N/A N/A j0 N/A xrange k N/A N/A j1 N/A xrange k N/A N/A N/A N/A N/A F N/A N/A i 2 N/A j0 N/A j1 0 N/A j0 N/A xrange k N/A N/A j1 N/A xrange k N/A N/A j2 N/A xrange k N/A N/A N/A i 2 N/A N/A N/A N/A N/A F N/A N/A i 2 N/A j0 N/A j1 N/A N/A N/A F N/A N/A N/A i 1 2 N/A j1 N/A EMPTY N/A N/A N/A N/A j1 j2 N/A j0 j1 N/A N/A N/A N/A N/A F N/A N/A i 2 N/A j0 N/A j1 N/A N/A N/A F N/A N/A N/A i 1 2 N/A j1 N/A j2 N/A N/A N/A j1 j2 N/A N/A N/A N/A N/A F N/A N/A i 2 N/A j0 N/A j1 N/A N/A N/A F N/A N/A N/A i 1 2 N/A j1 N/A j2 N/A ret 0 N/A j0 N/A xrange k N/A N/A j1 N/A xrange k N/A N/A ret N/A N/A N/A F N/A N/A n 2 N/A j0 N/A j1 N/A ret N/A numWays_MLE N/A N/A self n k N/A N/A N/A 
        DP
        let F[i][j][l] be the number of ways of painting for A[:i] with A[i-1] as color j and A[i-2] as color l
        :type n: int
        :type k: int
        :rtype: int
         N/A N/A n 1 N/A N/A 0 N/A F N/A N/A N/A 0 N/A _ N/A xrange k N/A _ N/A xrange k N/A _ N/A xrange N/A n 1 N/A EMPTY 0 N/A j0 N/A xrange k N/A N/A N/A N/A N/A F N/A 1 N/A j0 N/A EMPTY 1 N/A i N/A xrange 2 N/A n 1 N/A N/A j0 N/A xrange k N/A N/A j1 N/A xrange k N/A N/A j2 N/A xrange k N/A N/A N/A i 2 N/A N/A N/A N/A N/A F N/A i N/A j0 N/A j1 N/A N/A N/A F N/A N/A i 1 N/A j1 N/A EMPTY N/A N/A N/A N/A j1 j2 N/A j0 j1 N/A N/A N/A N/A N/A F N/A i N/A j0 N/A j1 N/A N/A N/A F N/A N/A i 1 N/A j1 N/A j2 N/A N/A N/A j1 j2 N/A N/A N/A N/A N/A F N/A i N/A j0 N/A j1 N/A N/A N/A F N/A N/A i 1 N/A j1 N/A j2 N/A ret 0 N/A j0 N/A xrange k N/A N/A j1 N/A xrange k N/A N/A ret N/A N/A N/A F N/A n N/A j0 N/A j1 N/A ret N/A N/A N/A N/A __name__ __main__ N/A N/A N/A N/A N/A N/A Solution numWays 3 2 6