企业官网建设流程全解析

Abstract#动态规划#二维DP#子序列匹配1. 题目题目LeetCode 115不同的子序列核心思路定义dp[i][j]为s[0..i]中t[0..j]作为子序列出现的次数。转移时若s[i] t[j]则可以选择匹配或不匹配dp[i][j] dp[i-1][j-1] dp[i-1][j]否则只能不匹配dp[i][j] dp[i-1][j]。复杂度时间复杂度O ( m n ) O(mn)O(mn)空间复杂度O ( n ) O(n)O(n)。2. 代码classSolution{public:intnumDistinct(string s,string t){intns.size(),mt.size();vectorunsignedlonglongdp(n,0);dp[0](s[0]t[0])?1:0;for(inti1;in;i)dp[i]dp[i-1](s[i]t[0]?1:0);intbackup,back;for(intj1;jm;j){backupdp[0];dp[0]0;for(inti1;in;i){backdp[i];dp[i](s[i]t[j]?backup:0)dp[i-1];backupback;}}return(int)dp[n-1];}};3. 心得直觉推导理性分析独立完成本题时是在确定状态之后通过模拟dp表生成过程中发现dp值生成规律从而推导出了状态转移方程的不得不说这也是一种解题方式。但是为了深化对题目的理解还是有必要从正向思考状态转移的含义。事实上对这类子序列问题一个常见的思考切入点就是考虑当前状态下的末尾字符。本题中t[j]可以看作是一个相对“确定”的因素因为它是被寻找的字符而问题的核心在于如何处理s[i]那么自然想到dp[i][j]的值在固定t[j]的情况下取决于我们是否选择s[i]加入当前已有的子序列s[0]...s[i - 1]。不选择是一种平凡的情况等价于考虑dp[i - 1][j]而选择则需要一个条件即两子序列末尾字符相同这样一来又在不选择的基础上再加上了dp[i - 1][j - 1]的情况。两种状态情况分析完毕再稍微用一下空间压缩就是最优解了这和我的直觉是匹配的。数据类型溢出题目说“测试用例保证结果在 32 位有符号整数范围内”但经过测试中间计算过程中dp[i-1][j-1] dp[i-1][j]的和可能超过 INT_MAX甚至 LONG_MAX。我一开始用了 int结果溢出改用 long long 仍然溢出在某些极端用例下比如 s 全为 ‘a’t 也全为 ‘a’结果会是指数级。最终发现必须用unsigned long long才能安全存储中间值。4. 相关题目LeetCode 1987不同的好子序列数目