DI序列的有效置换-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 给定一个字符串，长度为n，D代表前一个数比下一个数大而I代表前一个数比下一个数小
2. 求出在所有0-n的排列中，满足上面字符串所代表的排列两两之间大小比较的排列的个数

思路：

- 最大的那个数，可能出现在下面三种情况：
  - 出现在位置0，a[0]>a[1]
  - 出现在位置i，a[i]>a[i+1]且a[i]<a[i-1]
  - 出现在位置n，a[n]>a[n-1]
- 枚举最大的数出现的位置，假设为i，当i选定为最大的数后，剩下的数要分配给左右两边，有c(n, i)种情况，并且左右两边的队列互相独立
- 这时候左右两边分别成了一个命题相同的子问题，求出即可
- 注意：需要注意的是，不是所有的动态规划都需要用递推的方式求解。这道题可以选择另一种写法，就是递归+缓存，代码量会少不少

代码：

```java
class Solution {
    private static int[][] c;
    private static int MOD = 1000000007;
    private static int[][] cache = new int[202][202];

private void init() {
        c = new int[202][202];
        c[0][0] = 1;
        for (int i = 1;i <= 201;i++) {
            c[i][0] = 1;
            for (int j = 1;j < i;j++) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                if (c[i][j] >= MOD) {
                    c[i][j] -= MOD;
                }
            }
            c[i][i] = 1;
        }
    }

public int find(String S, int left, int right) {
        int ret = 0;
        if (right - left == 0) {
            return 1;
        }
        if (cache[left][right] != -1) {
            return cache[left][right];
        }
        if (S.charAt(left) == 'D') {
            ret += find(S, left + 1, right);
            if (ret >= MOD) {
                ret -= MOD;
            }
        }
        if (S.charAt(right - 1) == 'I') {
            ret += find(S, left, right - 1);
            if (ret >= MOD) {
                ret -= MOD;
            }
        }
        for (int i = left + 1;i < right;i++) {
            if (S.charAt(i) == 'D' && S.charAt(i - 1) == 'I') {
                ret += ((long) find(S, left, i - 1) * find(S, i + 1, right) % MOD) * c[right - left][i - left] % MOD;
                if (ret >= MOD) {
                    ret -= MOD;
                }
            }
        }
        if (ret == 0) {
            return cache[left][right] = 1;
        }
        return cache[left][right] = ret;
    }

public int numPermsDISequence(String S) {
        init();
        for (int i = 0;i < 202;i++) {
            for (int j = 0;j < 202;j++) {
                cache[i][j] = -1;
            }
        }
        int ret = find(S, 0, S.length());
        return ret;
    }
}
```

该分类下的相关小册推荐：

算法面试通关 50 讲

数据结构与算法(上)

业务开发实用算法精讲

数据结构与算法(下)

编程之道-算法面试(下)

数据结构与算法之美

编程之道-算法面试(上)