How many n-permutations match a given string that only tells where the permutation is increasing or decreasing or both? (DP)

Revision en5, by zxcv890, 2018-07-16 12:17:07

This question was featured in a ICPC Regional Contest. To summarize briefly, it gives a string consisting of 3 possible letters, 'I' (which stands for increasing), 'D' (decreasing) and/or '?' (both 'I' or 'D') to represent two consecutive numbers of an n-permutation (1 to n). Ex. the string 'IID' can fit the 4-permutations {1,3,4,2}, {1,2,4,3} and {2,3,4,1}. The task is given a string, find the number of possible permutations that fit the string in mod 10^9 + 7.

A working solution is found here. Can someone please clarify the recurrence relation to solve this dp?

Tags dynamic programming, combinatorics, uva 1650, permutation, dp


  Rev. Lang. By When Δ Comment
en5 English zxcv890 2018-07-16 12:17:07 0 (published)
en4 English zxcv890 2018-07-16 12:16:35 135 Tiny change: '{1,2,4,3} or {2,3,4,1}. Your task is g' -> '{1,2,4,3} and {2,3,4,1}. The task is g' (saved to drafts)
en3 English zxcv890 2018-07-16 10:32:10 0 (published)
en2 English zxcv890 2018-07-16 10:31:42 169
en1 English zxcv890 2018-07-16 10:26:43 736 Initial revision (saved to drafts)