Help Understanding Solution to Combinatorics / Dynamic Programming Question

Правка en1, от zxcv890, 2018-07-16 10:26:43

This question was featured in a ICPC Regional Contest. It gives a string of 'I' (increasing), 'D' (decreasing) and/or '?' (either increasing or decreasing) to represent two consecutive members of an n-permutation. ex. IID can be {1,2,4,3} or {2,3,4,1} etc. Your 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?

Теги dynamic programming, combinatorics, uva 1650, permutation, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский zxcv890 2018-07-16 12:17:07 0 (published)
en4 Английский 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 Английский zxcv890 2018-07-16 10:32:10 0 (published)
en2 Английский zxcv890 2018-07-16 10:31:42 169
en1 Английский zxcv890 2018-07-16 10:26:43 736 Initial revision (saved to drafts)