整数划分类DP

AcWing 900. 整数划分
方法1：完全背包求解恰好装满方案数
方法2：线性DP(集和分类需要考虑映射)
AcWing 1050. 鸣人的影分身
整数划分问题.pdf

903. DI 序列的有效排列

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

• “D” 意味着减少，或者
• “I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

• 如果 s[i] == ‘D’，那么 perm[i] > perm[i+1]，以及；
• 如果 s[i] == ‘I’，那么 perm[i] < perm[i+1]。

返回 有效排列** ** _perm的数量 _。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

示例 1：
输入：s = “DID” 输出：5 解释： (0, 1, 2, 3) 的五个有效排列是： (1, 0, 3, 2) (2, 0, 3, 1) (2, 1, 3, 0) (3, 0, 2, 1) (3, 1, 2, 0)
示例 2:
输入: s = “D” 输出: 1

提示:

• n == s.length
• 1 <= n <= 200
• s[i] 不是 ‘I’ 就是 ‘D’

思路：
难点在于如何表示状态
问题的规模取决于s的长度，故可考虑状态定义为
f[i][j]表示由[0, i]组成的满足s[0, i - 1]要求的且最后一位是j的排列
状态转移：
若s[i - 1] == 'D'最后一位可选的范围是0, i - 1]
不妨设最后一位是k (0 <= k <= i - 1)，有f[i][k] = f[i - 1][k] + f[i - 1][k + 1] + .. + f[i - 1][i - 1]
为什么是这样呢？考虑一一映射：
从右到左，将[0, i - 1]中所有在[k, i - 1]范围的数全部加一，仍满足s[0, i - 2]的要求，且由于第i - 1位数>= k，加一后变为> k因此满足s[0, i - 1]的要求，映射成立
从左到右，将[0, i - 1]中所有在[k + 1, i]范围的数全部减一，仍满足s[0, i - 2]的要求，且前i + 1个数正好是[0, i]，满足映射
若s[i - 1] == 'I'最后一位可选的范围是[1, i]
不妨设最后一位是k (1 <= k <= i)，有f[i][k] = f[i - 1][0] + f[i - 1][1] + .. + f[i - 1][k - 1]
推导同上
转移优化：
若s[i - 1] == 'D'，f[i][k] = f[i - 1][k] + f[i - 1][k + 1] + .. + f[i - 1][i - 1]
f[i][k + 1] = f[i - 1][k + 1] + f[i - 1][k + 2] + .. + f[i - 1][i - 1]
可得f[i][k] = f[i - 1][k] + f[i ][k + 1]
若s[i - 1] == 'I'，f[i][k] = f[i - 1][0] + f[i - 1][1] + .. + f[i - 1][k - 1]
f[i][k - 1] = f[i - 1][0] + f[i - 1][1] + .. + f[i - 1][k - 2]
可得f[i][k] = f[i][k - 1] + f[i - 1][k - 1]
初始化：f[0][0] = 1
最终结果res = f[n][0] + f[n][1] + ... + f[n][n]

class Solution {
    static final int MOD = (int)(1e9 + 7);
    public int numPermsDISequence(String s) {
        int n = s.length();
        int[][] f = new int[n + 1][n + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == 'D') {
                for (int j = i - 1; j >= 0; j--) {
                    f[i][j] = (f[i][j + 1] + f[i - 1][j]) % MOD;
                }
            } else {
                for (int j = 1; j <= i; j++) {
                    f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % MOD;
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= n; i++)
            res = (res + f[n][i]) % MOD;
        return res;
    }
}