具体方案

动态规划算法虽然不擅于找所有方案
但是找最优值的具体方案还是可以的

这种情况建议记忆化搜索

倒推法

记录每个状态的最优值是从哪个前继状态来的
通常需要一个和状态数组同样维度的数组
prev[i]记录使得dp[i]获得最优值的那个j是准
j是方程dp[i]=max{dp[j]]+1}里的j

改动要点

1. prev数组记录前继最优状态，有时也不需要prev数组，倒推的时候一步一步推prev即可，参考lc368 最大整除子集
2. max()的写法要改为f的写法
3. 找到最长龙的结尾，从结尾倒推出整条龙

---

def longestIncreasingSubsequence(self,nums):
    if nums is None or not nums:
    	return 0
    # state: dp[i]表示从左到右跳到i的最长sequence的长度
    # initialization: dp[0..n-1]1
    dp = [1] * len(nums)
    # prev[i]代表dp[i门的最优值是从哪个dp[j门算过来的
    prev = [-1] * len(nums)
    
    # function dp[i]=max{dp[j]+1},j<i and nums[j]<nums[i]
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
                
    # answer: max(dp[0..n-1])
    longest, last =0, -1
    for i in range(len(nums)):
        if dp[i]>longest:
            longest = dp[i]
            last = i
	
    path = []
    while last != -1:
        path.append(nums[last])
        last = prev[last]
	print(path[::-1])
    
    return longest

状压法

满足如下条件，可以使用状态压缩DP的方法

1. 顺序不重要（只要方案集合）
2. 答案长度不大（int < 32, long < 64）

public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
    var sid = new HashMap<String, Integer>();
    int m = reqSkills.length;
    for (int i = 0; i < m; ++i)
        sid.put(reqSkills[i], i); // 字符串映射到下标

    int n = people.size();
    var mask = new int[n];
    for (int i = 0; i < n; ++i)
        for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask[i]
            mask[i] |= 1 << sid.get(s);

    int u = 1 << m;
    var ids = new long[u]; // ids[j] 表示 f[j] 对应的 people 下标集合
    var f = new int[u]; // f[j] 表示并集为 j 至少要选的 people 个数
    Arrays.fill(f, Integer.MAX_VALUE);
    f[0] = 0;
    for (int j = 0; j < u - 1; ++j) // f[u-1] 无需计算
        if (f[j] < Integer.MAX_VALUE)
            for (int i = 0; i < n; ++i)
                if (f[j] + 1 < f[j | mask[i]]) {
                    f[j | mask[i]] = f[j] + 1; // 刷表：用 f[j] 去更新其它状态
                    ids[j | mask[i]] = ids[j] | (1L << i);
                }

    long res = ids[u - 1];
    var ans = new int[Long.bitCount(res)];
    for (int i = 0, j = 0; i < n; ++i)
        if (((res >> i) & 1) != 0)
            ans[j++] = i; // 所有在 res 中的下标
    return ans;
}

具体方案

动态规划算法虽然不擅于找所有方案
但是找最优值的具体方案还是可以的

倒推法

记录每个状态的最优值是从哪个前继状态来的
通常需要一个和状态数组同样维度的数组
prev[i]记录使得dp[i]获得最优值的那个j是准
j是方程dp[i]=max{dp[j]]+1}里的j

改动要点

1. prev数组记录前继最优状态
2. max()的写法要改为f的写法
3. 找到最长龙的结尾，从结尾倒推出整条龙

---

def longestIncreasingSubsequence(self,nums):
    if nums is None or not nums:
    	return 0
    # state: dp[i]表示从左到右跳到i的最长sequence的长度
    # initialization: dp[0..n-1]1
    dp = [1] * len(nums)
    # prev[i]代表dp[i门的最优值是从哪个dp[j门算过来的
    prev = [-1] * len(nums)
    
    # function dp[i]=max{dp[j]+1},j<i and nums[j]<nums[i]
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
                
    # answer: max(dp[0..n-1])
    longest, last =0, -1
    for i in range(len(nums)):
        if dp[i]>longest:
            longest = dp[i]
            last = i
	
    path = []
    while last != -1:
        path.append(nums[last])
        last = prev[last]
	print(path[::-1])
    
    return longest

回顾一下经典算法的简称

状压法

如果顺序不重要，且答案长度不大的话(int < 32, long < 64)，可以使用状态压缩DP的方法

public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
    var sid = new HashMap<String, Integer>();
    int m = reqSkills.length;
    for (int i = 0; i < m; ++i)
        sid.put(reqSkills[i], i); // 字符串映射到下标

    int n = people.size();
    var mask = new int[n];
    for (int i = 0; i < n; ++i)
        for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask[i]
            mask[i] |= 1 << sid.get(s);

    int u = 1 << m;
    var ids = new long[u]; // ids[j] 表示 f[j] 对应的 people 下标集合
    var f = new int[u]; // f[j] 表示并集为 j 至少要选的 people 个数
    Arrays.fill(f, Integer.MAX_VALUE);
    f[0] = 0;
    for (int j = 0; j < u - 1; ++j) // f[u-1] 无需计算
        if (f[j] < Integer.MAX_VALUE)
            for (int i = 0; i < n; ++i)
                if (f[j] + 1 < f[j | mask[i]]) {
                    f[j | mask[i]] = f[j] + 1; // 刷表：用 f[j] 去更新其它状态
                    ids[j | mask[i]] = ids[j] | (1L << i);
                }

    long res = ids[u - 1];
    var ans = new int[Long.bitCount(res)];
    for (int i = 0, j = 0; i < n; ++i)
        if (((res >> i) & 1) > 0)
            ans[j++] = i; // 所有在 res 中的下标
    return ans;
}