首页

# 区间 DP

LeetCode 上的 **【877. 石子游戏】，难度为【中等】**。

典型的区间 DP 问题：大区间状态值依赖小区间状态值。

假设 f[x][y] 表示的是先手在 [x,y] 区间的总数差值，那么最后只需要 return f[1][n] > 0 即可。从一般性推导递推式， f[l][r] ，如果先手先拿左边的，那么之后就是后手变先手， f[l+1][r] 就是 f[l][r] 中后手的总数差值，所以先拿左边得到的差值就是 p[l]-f[l+1][r] 。同理，拿右边得到的差值就是 p[r]-f[l][r-1] 。因为两边都想赢，所以 f[l][r] = Math.max(p[l]-f[l+1][r],p[r]-f[l][r-1]) 。

相关代码：

public boolean stoneGame(int[] p) {
    int n = p.length;
    int[][] f = new int[n+2][n+2];
    
    for(int len = 1; len <= n; len++) { // 枚举区间长度
        for(int l = 1; l + len -1 <= n; l++) { // 枚举左端点
            int r = l + len - 1; // 右端点
            f[l][r] = Math.max(p[l-1] - f[l+1][r], p[r-1],f[l][r-1]);
        }
    }
    return f[1][n] > 0;
}

总结：大区间依赖小区间，所以在 dp 时，可以先枚举区间长度。

当然，这道题，作为博弈问题，其实是先手必赢的局面。

扩展一下博弈思路，首先石子总和为奇数，总数为偶数，满足这么一个特性：均分两堆 AB，AB 堆各自石子总和必不可能相同。所以先手在拿的时候，可以将石子数组划分两堆：

  • 原数组：C C C C C C
  • 划分后：A B A B A B

那么 sum_A 和 sum_B 必定有一个更大，先手可以保证总是拿到 A 或者 B。如果 A 堆更到，那先手只需要每次都拿 A 即可（后手每次受 A 影响，只能拿 B）。

其他的区间 DP 练习题：

  • 最长回文子序列

参考：

  • 三叶姐：https://mp.weixin.qq.com/s/Se2Aw_q74vYlApF7H6OUVw

# 序列 DP

LeetCode 上的 **【139. 单词拆分】，难度为【中等】**。

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

调整字符串 s 以及 dp 数组下标从 1 开始。

定义 f[i] 是前 i 个字符，能否使用 wordDict 拼凑： f[i]=true 代表 s[1...i] 能够使用 wordDict 所凑成，反之则不能。

数组转移： f[i] 需要考虑 s[1...i] 范围内的字符，如果 f[j-1]=true 且 s[j..i] 能够被拼凑出来，就说明 f[i] = true 。所以我们需要做的就是枚举 1~i 。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> setWord = new HashSet<>();
        for(String word : wordDict) setWord.add(word);
        int n = s.length();
        boolean[] f = new boolean[n+1];
        f[0] = true;
        for(int i = 1;i <= n;i++) {
            for(int j = 1 ; j <= i && !f[i] ; j++) {
                if(f[j-1] && setWord.contains(s.substring(j-1,i))) f[i] = true;
            }
        }
        return f[n];
    }
}
执行用时为 7ms，其实还可以更快，在底层循环中，我们的目的是在 1~i 中间插一块使其分为两个区间（i==j 时为一个区间），其实可以不用遍历取划分区间，假设给定单词数组里面，单词长度分别是 3，5，6。那么划分 s[i-1,i] 这样的区间是没有意义的，优化代码如下：
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> setWord = new HashSet<>();
        Set<Integer> setLen = new HashSet<>();
        for(String word : wordDict){
            setWord.add(word);// 实现快速查询
            setLen.add(word.length());
        } 
        int n = s.length();
        boolean[] f = new boolean[n+1];
        f[0] = true;
        for(int i = 1 ; i <= n ; i++) {
            for(Integer len : setLen) {
                // 将两个判断起来快一点的条件放前面
                if(i >= len && f[i-len] && setWord.contains(s.substring(i-len, i))) {
                    f[i] = true;break;
                }
            }
        }
        return f[n];
    }
}
线性 dp 与序列 dp 的区别：
  • 线性 dp 强调【状态转移所依赖的前驱状态】是由给定数组所提供的，也就是 f[i][..] 依赖 f[i-1][...] 。限定了线性 dp 复杂度是简单由【状态数量】决定的。
  • 序列 dp 需要结合题意来寻找前驱状态，需要自身寻找拓扑序关系（如本题需要自己枚举的方式寻找左端点，从而找到可转移的前驱状态 f[j-1] 。限定了序列 dp 复杂度是由【状态数 + 找前驱】的复杂度决定的。
学习三叶姐的公众号：【常见题型总结】序列 DP 模板题（总结【线性 DP】和【序列 DP】本质区别）。
# 数位 DP
LeetCode 上的 **【902. 最大为 N 的数字组合】，难度为【困难】**。
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 来写的数字。例如，如果 ，我们可以写数字，如 '13' , '551' , 和 '1351315' 。
返回 可以生成的小于或等于给定整数 的正整数的个数 。
示例 1：
输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
其实就是数组中组合起来小于 n 的数的个数。
class Solution {
    int[] nums;
    int dp(int x) {
        List<Integer> list = new ArrayList<>();
        while (x != 0) {
            list.add(x % 10);
            x /= 10;
        }
        int n = list.size(), m = nums.length, ans = 0;
        // 位数和 x 相同
        for (int i = n - 1, p = 1; i >= 0; i--, p++) {
            int cur = list.get(i);
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= cur) l = mid;
                else r = mid - 1;
            }
            if (nums[r] > cur) {
                break;
            } else if (nums[r] == cur) {
                ans += r * (int) Math.pow(m, (n - p));
                if (i == 0) ans++;
            } else if (nums[r] < cur) {
                ans += (r + 1) * (int) Math.pow(m, (n - p));
                break;
            }
        }
        // 位数比 x 少的
        for (int i = 1, last = 1; i < n; i++) {
            int cur = last * m;
            ans += cur; last = cur;
        }
        return ans;
    }
    public int atMostNGivenDigitSet(String[] digits, int max) {
        int n = digits.length;
        nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(digits[i]);
        return dp(max);
    }
}
# 状态机 DP
学习三叶姐的文章：【综合笔试题】难度 2.5/5，状态机序列 DP 运用题
LeetCode 上的【1218. 最长定差子序列】，难度为 **「中等」**。
给你一个整数数组 arr 和一个整数 difference ，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
本题的数据范围在 10^5 之内，朴素的序列 dp 会超时，所以需要使用点技巧，用 HashMap 存储上次 x 出现过的最近的位置：
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length, max = 1;
        int[] f = new int[n];
        Map<Integer,Integer> map = new HashMap<>();
        Arrays.fill(f,1);
        // 朴素的序列 dp 会超时
        map.put(arr[0],0);
        for(int i = 1; i < n; i++) {
            int t = arr[i]-difference;
            if(map.containsKey(t)) f[i] = Math.max(f[i], f[map.get(t)]+1);
            max = Math.max(f[i], max);
            map.put(arr[i],i); // 贪心思想
        }
        return max;
    }
}
这和状态机有什么关系呢？
状态机这类问题往往是强调某一个阶段和上一个阶段之间的联系，且一个阶段里面有多种状态（比如说 “有” 和 “无”）。
是不是和序列 DP 很像，其实状态机 DP 就是很常见的 DP 问题，动态规划也就是根据前面有限的状态转移到当前状态，不要被名词吓住了。
这里说一下状态压缩：就是用二进制数来表示动态规划状态转移过程中的状态。因为二进制只有 0 和 1，所以表示的状态一般就是有 / 无，或者完成 / 未完成这种状态。状态压缩的题目，一般都会有非常明显的标志：如果你看到有一个参数的数值小于 20，同时这道题目中有涉及到是否选取、是否使用这样的二元状态，那么这道题目很可能就是一道状态压缩的题目。
状态压缩的解释出自：https://leetcode.cn/problems/stickers-to-spell-word/solution/zhuang-tai-ya-suo-dpji-you-hua-by-lucifer1004/
# LCS 模板
LCS 就是最长公共子序列，LeetCode 上的 **【1143. 最长公共子序列】】，难度为【中等】**。
给定两个字符串，找出最长公共子序列。
LCS 这类题，都使用如下 **【状态定义】**：
f[i][j] 表示考虑 s1 前 i 个字符和考虑 s2 前 j 个字符，形成的最长公共子序列长度。有了【状态定义】，就可以得到【转移方程】：
  • 如果 s1[i] == s2[j] ： f[i][j] = f[i-1][j-1]+1 。
  • 如果 s1[i] != s2[j] ： f[i][j] = Math.max(f[i-1][j],f[i][j-1]) 。
编码细节：可以在两个字符串前面加上一个空格，这样就可以将 f[i][0] 和 f[0][j] 初始化为 1。
public int fun(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    s1 = " " + s1;s2 = " " + s2;
    
    for(int i = 0 ; i <= n ; i++) f[i][0] = 1;
    for(int j = 0 ; j <= m ; j++) f[0][j] = 1;
    
    for(int i = 1 ; i <= n ;i++) {
        for(int j = 1 ; j <= m ; j++) {
            if(s1[i] == s2[j]) f[i][j] = f[i-1][j-1] + 1;
            else f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
        }
    }
    return f[i][j] - 1;
}
如何通过 f 数组构造出最长公共子序列：
StringBuffer sb = new StringBuffer();
int i = n , j = m;
while(i > 0 && j > 0) {
    if(s1[i] == s2[j]) {
        sb.append(s1[i]);
        i--;j--;
    } else if(f[i][j] == f[i-1][j]) {
        //s1 [i] 没有在 s1 (0,i)，s2 (0,j) 的最长公共子序列中
        i--;
    } else j--;
}
return sb.reverse().toString();
类似题还有 **【1092. 最短公共超序列】**。
学习三叶姐的公众号：【面试高频题】难度 1.5/5，LCS 模板题。
# 经典题目复现
# 最长递增子序列
该系列题在牛客分别是三种要求：
  • 找最长上升子序列，时间复杂度 O (n^2)
  • 找最长上升子序列，时间复杂度 O (nlogn)
  • 最长上升子序列可能有多个，请返回字典序最小的那个子序列，时间复杂度 O (nlogn)
第三种比二种多的其实就是保存状态，第二种最重要的就是二分查找，我们先看一下第二种的代码
/* 有些是要求给出最长的子序列，有些要求给出长度即可 */
public int LIS(int[] arr) {
    int n = arr.lenght, l = 0, r = 0, riht = 0, m = 0, res = 1;
    int[] ends = new int[n];
    ends[0] = arr[0];
    
    for(int i = 1; i < n; i++) {
        l = 0; r = right; // 开始二分
        while(l <= r) {
            m = (l + r) >> 1;
            if(arr[i] > ends[m]) l = m + 1; // 肯定不能覆盖比自己小的
            else r = m - 1; // 考虑 1,3 插入 2 的情况，尽管 3 暂时被 m-1 了，但是 l 还会加回来
        }
        //l 是可以直接覆盖的
    	right = Math.max(right, l);
        res = Math.max(res, l+1);
        ends[l] = arr[i];
    }
    return res;
}
再来看第三种，主要就是保存每次更新的状态
public int[] LIS(int[] arr) {
    int n = arr.length, l = 0, r = 0, right = 0, m = 0;
    int[] ends = new int[n];
    List<Integer>[] status = new List[n];
    
    ends[0] = arr[0];
    status[0] = new ArrayList<>();
    status[0].add(arr[0]);
    
    for(int i = 1; i < n; i++) {
        l = 0; r = right;
        
        while(l <= r) {
            m = (l + r) >> 1;
            if(ends[m] < arr[i]) l = m+1;
            else r = m-1;
        }
        //l 是绝对可以覆盖的
        if(l == 0) {
            status[0].set(0, arr[i]);
        } else {
            ArrayList<Integer> t = new ArrayList<>(status[l-1]);
            t.add(arr[i]);
            right = Math.max(right, l);
            status[l] = t;
        }
        ends[l] = arr[i];
    }
    
    int[] res = new int[right+1];
    for(int i = 0; i <= right; i++) {
        res[i] = status[right].get(i);
    }
    return res;
}