前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 49，周二，坚持不了一点~

题目详情

[300] 最长递增子序列

题目描述

300 最长递增子序列

解题思路

前提：最大递增子序列的长度
思路：动态规划 dp[i]: 在数组的[0, i]中最长严格递增子序列的长度，j遍历[0, i], 寻找其中的递增子序列, dp[i] = max(dp[i], dp[j] + 1)
重点：递推公式的推导、dp数组初始化

代码实现

C语言

动态规划

// 动态规划 dp[i]: 在数组的[0, i]中最长严格递增子序列的长度
// j遍历[0, i], 寻找其中的递增子序列, dp[i] = max(dp[i], dp[j] + 1)int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}int lengthOfLIS(int* nums, int numsSize) {int dp[numsSize];// dp初始化dp[0] = 1;int result = dp[0];// 遍历for (int i = 1; i < numsSize; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = maxFun(dp[i], dp[j] + 1);}}result = maxFun(result, dp[i]);}return result;
}

[674] 最长连续递增序列

题目描述

674 最长连续递增序列

解题思路

前提：最长连续递增子序列的长度
思路：动态规划 dp[i]: 在数组的[0, i]中最长连续递增子序列的长度，if (nums[i] > nums[i-1]) dp[i] = dp[i - 1] + 1
重点：递推公式的推导、dp数组初始化

代码实现

C语言

动态规划

// 动态规划 dp[i]: 在数组[0,i]中连续递增子序列的最大长度
// if (nums[i] > nums[i-1]) dp[i] = dp[i - 1] + 1int findLengthOfLCIS(int* nums, int numsSize) {int dp[numsSize];// dp初始化dp[0] = 1;int result = dp[0];// 遍历for (int i = 1; i < numsSize; i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;} else {dp[i] = 1;}result = result < dp[i] ? dp[i] : result;}return result;
}

贪心算法

// 贪心算法, 递增则count++,否则count = 1int findLengthOfLCIS(int* nums, int numsSize) {int count = 1;int result = count;// 遍历for (int i = 1; i < numsSize; i++) {if (nums[i] > nums[i - 1]) {count++;} else {count = 1;}result = result < count ? count : result;}return result;
}

[718] 最长重复子数组

题目描述

718 最长重复子数组

解题思路

前提：最长重复子数组
思路：动态规划 滚动数组dp[j]: nums1的[0, i-1]与nums2的[0, j-1]的最长重复子数组的长度, if (nums[i-1] == nums[j-1]) dp[j] = dp[j-1]+1
重点：递推公式的推导、dp数组初始化

代码实现

C语言

dp[i][j]

// 动态规划 dp[i][j]: nums1的[0, i-1]与nums2的[0, j-1]的最长重复子数组的长度
// if (nums[i-1] == nums[j-1]) dp[i][j] = dp[i-1][j-1]+1int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums1Size + 1][nums2Size + 1];int result = 0;// dp数组初始化,实际从1开始for (int i = 0; i <= nums1Size; i++) {dp[i][0] = 0;}for (int j = 1; j <= nums2Size; j++) {dp[0][j] = 0;}// 遍历for (int i = 1; i <= nums1Size; i++) {for (int j = 1; j <= nums2Size; j++) {dp[i][j] = 0;if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}result = result < dp[i][j] ? dp[i][j] : result;}}return result;
}

dp][j]

// 动态规划 滚动数组dp[j]: nums1的[0, i-1]与nums2的[0, j-1]的最长重复子数组的长度
// if (nums[i-1] == nums[j-1]) dp[j] = dp[j-1]+1int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums2Size + 1];int result = 0;// dp数组初始化,实际从1开始for (int k = 0; k <= nums2Size; k++) {dp[k] = 0;}// 遍历nums1, 并从后往前遍历nums2for (int i = 1; i <= nums1Size; i++) {for (int j = nums2Size; j >= 1; j--) {dp[j] = 0;if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;}result = result < dp[j] ? dp[j] : result;}}return result;
}

今日收获

1. 动态规划