[This](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4525) 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](https://github.com/morris821028/UVa/blob/master/temp/1650%20-%20Number%20String.cpp). Can someone please clarify the recurrence relation to solve this dp?
↵
A working solution is found [here](https://github.com/morris821028/UVa/blob/master/temp/1650%20-%20Number%20String.cpp). Can someone please clarify the recurrence relation to solve this dp?
