Modified coin-change problem with constraints on valid coin combination patterns

Model the missing constraint

Ordinary coin change uses a state such as dp[amount] or dp[i][amount], but a rule about valid patterns can require more information: last denomination, count of a coin, parity, ordering, or whether a special coin was used. Ask for that exact rule and an example before choosing a recurrence.

Then define dp[position][sum][constraintState] as the number, minimum count, or feasibility result required by the prompt. Make the state contain only information needed for future validity. Initialize the empty construction at sum zero, reject transitions that violate the pattern, and state whether order makes two sequences distinct. A simple baseline enumerates combinations exponentially; the DP is typically O(n * target * S) time and O(target * S) or O(n * target * S) space, where S is the number of constraint states. Test target zero, unavailable sums, repeated denominations, and boundary-valid patterns.