Skip to content

903. Valid Permutations for DI Sequence

903. Valid Permutations for DI Sequence

题目: https://leetcode.com/problems/valid-permutations-for-di-sequence

难度: 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)种情况，并且左右两边的队列互相独立
  • 这时候左右两边分别成了一个命题相同的子问题，求出即可
  • 注意：需要注意的是，不是所有的动态规划都需要用递推的方式求解。这道题可以选择另一种写法，就是递归+缓存，代码量会少不少

代码：

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;
    }
}
回到顶部