动态规划专练:力扣第1035、392题

力扣第1035题-不相交的线

1.本题和力扣第1143题-最长公共子序列一模一样，不能让线相交本质上就是不能走回头路，相对顺序不能改变，即公共子序列需要按顺序排列。完整代码如下：

1. int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) { 2. // 一维滚动dp数组，dp[j]表示nums1前i个数字、nums2前j个数字能绘制的最多不相交连线 3. int dp[nums2Size + 1]; 4. memset(dp, 0, sizeof(dp)); 5. 6. for (int i = 1; i <= nums1Size; i++){ 7. // pre存储二维dp[i-1][j-1]的值，即本轮更新前的dp[j-1] 8. int pre = dp[0]; 9. for (int j = 1; j <= nums2Size; j++){ 10. // 保存更新前dp[j]，作为下一轮j+1的pre 11. int cur = dp[j]; 12. if (nums1[i - 1] == nums2[j - 1]){ 13. // 数字相等，可以连线，数量等于左上角状态+1 14. dp[j] = pre + 1; 15. } else { 16. // 数字不等，继承上方或左侧更大的连线数 17. dp[j] = fmax(dp[j], dp[j - 1]); 18. } 19. pre = cur; 20. } 21. } 22. 23. return dp[nums2Size]; 24. }

该算法时间复杂度为O(nums1Size * nums2Size)，空间复杂度为O(nums2Size)。

力扣第392题-判断子序列

1.可以使用双指针，t的指针cur2一直+1，s的指针cur1只有在两个指针所指字符相等的时候才+1，最后如果cur1 == len1就说明s是t的子集，否则就不是。完整代码如下：

1. bool isSubsequence(char* s, char* t) { 2. int len1 = strlen(s); 3. int len2 = strlen(t); 4. // s长度大于t，不可能是子序列 5. if (len1 > len2) return false; 6. 7. // cur1：s匹配指针，cur2：t遍历指针 8. int cur1 = 0, cur2 = 0; 9. while (cur1 < len1 && cur2 < len2){ 10. // 字符匹配，s指针后移 11. if (s[cur1] == t[cur2]){ 12. cur1++; 13. } 14. // t指针持续后移 15. cur2++; 16. } 17. 18. // s全部匹配完成则为子序列 19. if (cur1 == len1) return true; 20. return false; 21. }

该算法时间复杂度为O(m + n)，空间复杂度为O(1)（m和n为字符串s和t的长度）。

2.本题也可以使用动态规划，本质上和力扣第1143题-最长公共子序列一模一样，只不过字符串s一定不会删除字符。最后只需要判断dp[len2]是否等于len1即可判断是否全部匹配。完整代码如下：

1. bool isSubsequence(char* s, char* t) { 2. int len1 = strlen(s); 3. int len2 = strlen(t); 4. // s更长一定不可能是子序列，直接返回false 5. if (len1 > len2) return false; 6. 7. // 一维滚动dp数组，dp[j]代表s前i个字符、t前j个字符的最长公共子序列长度 8. int dp[len2 + 1]; 9. memset(dp, 0, sizeof(dp)); 10. for (int i = 1; i <= len1; i++){ 11. // pre保存二维dp[i-1][j-1]，更新前左上角的值 12. int pre = dp[0]; 13. for (int j = 1; j <= len2; j++){ 14. // 记录更新前dp[j]，作为下一轮j+1的pre 15. int cur = dp[j]; 16. if (s[i - 1] == t[j - 1]){ 17. // 字符匹配，公共子序列长度 = 左上角值 + 1 18. dp[j] = pre + 1; 19. } else { 20. // 字符不匹配，取上方旧值或左侧新值较大者 21. dp[j] = fmax(dp[j], dp[j - 1]); 22. } 23. pre = cur; 24. } 25. } 26. // 若最长公共子序列长度等于s全长，说明s是t的子序列 27. return dp[len2] == len1; 28. }

该算法时间复杂度为O(m * n)，空间复杂度为O(n)。