代码随想录算法训练营第四十四天|Day44 动态规划

1143.最长公共子序列

视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ

https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
int longestCommonSubsequence(char* text1, char* text2) {int text1Len = strlen(text1);int text2Len = strlen(text2);int dp[text1Len + 1][text2Len + 1];memset(dp, 0, sizeof (dp));for (int i = 1; i <= text1Len; ++i) {for (int j = 1; j <= text2Len; ++j) {if(text1[i - 1] == text2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;} else{dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1Len][text2Len];
}

学习反思

两个字符串的最长公共子序列的长度。其中使用了动态规划的思想。首先，定义了一个宏函数max，用来返回两个数中的较大值。然后，使用strlen函数获取两个字符串的长度。接下来，定义了一个二维数组dp，用来保存最长公共子序列的长度。数组的行数为text1Len + 1，列数为text2Len + 1。然后，使用memset函数将dp数组初始化为0。接下来，使用两个for循环遍历两个字符串的字符。如果两个字符相等，说明可以将这两个字符加入到最长公共子序列中，所以dp[i][j]的值为dp[i-1][j-1]+1。如果两个字符不相等，说明不能将这两个字符同时加入到最长公共子序列中，所以dp[i][j]的值为dp[i-1][j]和dp[i][j-1]中的较大值。最后，返回dp[text1Len][text2Len]，即为最长公共子序列的长度。这段代码的时间复杂度为O(mn)，其中m为text1的长度，n为text2的长度。因为需要遍历两个字符串的所有字符。空间复杂度为O(mn).

1035.不相交的线

视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP

https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html

思路

int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums1Size + 1][nums2Size + 1];memset(dp, 0, sizeof(dp));for (int i = 1; i <= nums1Size; i++) {for (int j = 1; j <= nums2Size; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1; } else {dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; }}}return dp[nums1Size][nums2Size];
}

学习反思

两个数组之间的最大不相交连线数。其中使用了动态规划的思想。首先，定义了一个二维数组dp，用来保存最大不相交连线数。数组的行数为nums1Size + 1，列数为nums2Size + 1。然后，使用memset函数将dp数组初始化为0。接下来，使用两个for循环遍历两个数组的元素。如果两个元素相等，说明可以将这两个元素连线，所以dp[i][j]的值为dp[i-1][j-1]+1。如果两个元素不相等，说明不能将这两个元素连线，所以dp[i][j]的值为dp[i-1][j]和dp[i][j-1]中的较大值。最后，返回dp[nums1Size][nums2Size]，即为最大不相交连线数。这段代码的时间复杂度为O(mn)，其中m为nums1的长度，n为nums2的长度。因为需要遍历两个数组的所有元素。空间复杂度为O(mn)。

53. 最大子序和

视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

思路

int maxSubArray(int* nums, int numsSize) {if (numsSize == 0) {return 0; }int maxCurrent = nums[0]; int maxGlobal = nums[0];   for (int i = 1; i < numsSize; i++) {maxCurrent = (nums[i] > maxCurrent + nums[i]) ? nums[i] : (maxCurrent + nums[i]);if (maxCurrent > maxGlobal) {maxGlobal = maxCurrent; }}return maxGlobal; 
}

学习反思

求解数组中的最大子数组和问题，使用了动态规划的思想。首先，判断数组的长度是否为0，如果为0，则直接返回0。然后，定义两个变量maxCurrent和maxGlobal，分别用来表示当前子数组的最大和和全局最大和。初始时，它们都被赋值为数组的第一个元素。接下来，使用一个for循环遍历数组的元素。在循环中，通过比较当前元素和当前元素加上前一个最大子数组和的值，选择一个较大的值作为新的最大子数组和。这样可以保证最大子数组和的连续性。然后，判断新的最大子数组和是否大于全局最大和，如果是，将其更新为全局最大和。最后，返回全局最大和，即为数组中的最大子数组和。段时间复杂度为O(n)，其中n为numsSize，即数组的长度。因为只需要遍历一次数组。空间复杂度为O(1)。

392.判断子序列

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

思路

bool isSubsequence(char* s, char* t) {int sIndex = 0;int tIndex = 0;while (t[tIndex] != '\0') {if (s[sIndex] == t[tIndex]) {sIndex++;}if (s[sIndex] == '\0') {return true;}tIndex++;}return s[sIndex] == '\0';
}

学习反思

判断字符串s是否是字符串t的子序列。在这段代码中，使用了两个指针sIndex和tIndex来分别指向s和t的字符位置。代码的逻辑是，首先初始化sIndex和tIndex为0，然后开始循环，循环条件是t[tIndex]不等于字符串结束符'\0'。在循环中，首先判断s[sIndex]是否等于t[tIndex]，如果相等，则sIndex自增1，表示已经匹配了s的一个字符。然后，判断s[sIndex]是否为结束符'\0'，如果是，则表示s已经全部匹配完了，是t的子序列，返回true。否则，tIndex自增1，继续循环。如果循环结束后，s[sIndex]仍然为结束符'\0'，则表示s已经全部匹配完了，是t的子序列，返回true。否则，返回false。这段代码的时间复杂度为O(n)，其中n为字符串t的长度。