[LeetCode]Valid Permutations for DI Sequence

递归的思路比较好想，因为我们当前位的选择是取决于上一位填的数字x，和剩下的可选的数有多少个比x大或者小的。具体来说，假设输入的string长度为n，我们一共有n + 1个可选的数，假设我们要填idx为i的数，剩下n + 1 - i个数，假设大于x的数有k个：

• 如果x对应的字符是D，那么我们这次必须要选比x小的数，那么这个选择一共有n + 1 - i - k个。假设选择了第m大的(从0开始)，下一次递归idx + 1, 比之前选的数大的就有n + 1 - i - (m + 1) = n - i - m个
• 如果x对应的字符是I，同理我们要选bix大的数，这个选择有k个，假设我们选择了这k个数中第m大的(从0开始)，下一次递归idx + 1，比之前选的数大的就有k - (m + 1)个

我们根据这个思路递归即可，然后注意保存每一次递归的值避免重复的计算。时间复杂度O(n ^ 3)，空间复杂度O(n ^ 2)。代码如下：

上面是top down的方法，下面我们分析一下bottom up怎么做。如果我们用dp[i][j]表示填到i位置的时候，剩下的数字还有j个比i位置的数字小的情况下，方法的总数。对于dp[i][j]来说，如果i - 1位对应的字符为D，那么如果要取完i数字之后还有j个比i位置的数小的话，我们只能从dp[i - 1][k]转移过来 ，其中j + 1 <= k <= n - i，否则的话取完之后只能剩下不到j个数。同理如果i - 1位字符为I，我们只能从dp[i - 1][k]转移过来 ，其中0 <= k <= j，否则取完之后必定剩下大于j个数。那么我们有递推方程：

• dp[i][j] = sum(dp[i - 1][k]), where j + 1 <= k <= n - i and S[i - 1] == 'D'
• dp[i][j] = sum(dp[i - 1][k]), where 0 <= k <= j and S[i - 1] == 'I'

时间复杂度O(n^3)，空间复杂度O(n^2)，代码如下：

这个方法还可以优化，比如当i - 1对应的字符是I的话，dp[i][j]可以利用dp[i][j - 1]的结果，同理D的话也是：

• dp[i][j] = dp[i][j - 1] + dp[i - 1][j], S[i - 1] == 'I', 从左向右遍历
• dp[i][j] = dp[i][j + 1] + dp[i - 1][j], S[i - 1] == 'D', 从右向左遍历

时间复杂度可以优化到O(n^2)。代码如下：