算法日记 35 day 动态规划
今天都是些比较简单的题，看看题目吧。
题目：最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
题目分析：
五部曲走起。dp[i]表示从0-i的区间内，最长的递增子序列长度为dp[i]。递推公式：
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);初始化全为1即可。
public class Solution {
public int LengthOfLIS(int[] nums) {
if(nums.Length<=1) return nums.Length;
int[] dp=new int[nums.Length];
Array.Fill(dp,1);
int res=0;
for(int i=1;i<nums.Length;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.Max(dp[i],dp[j]+1);
}
}
if(dp[i]>res) res=dp[i];
}
return res;
}
}题目：最长连续递增序列
674. 最长连续递增序列 - 力扣（LeetCode）
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
题目分析：
同样是求解递增序列，不过本题要求连续，这意味着一个状态必定是由他的上一个状态改变过来的。dp[i]表示从0-i的区间内，最长的连续递增序列长度为dp[i]。递推公式：
如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即：dp[i] = dp[i - 1] + 1;
public class Solution {
public int FindLengthOfLCIS(int[] nums) {
if(nums.Length<=1) return nums.Length;
int[] dp=new int[nums.Length];
Array.Fill(dp,1);
int res=1;
for(int i=1;i<nums.Length;i++){
if(nums[i]>nums[i-1]){
dp[i]=dp[i-1]+1;
}
res=Math.Max(res,dp[i]);
}
return res;
}
}题目：最长重复子数组
718. 最长重复子数组 - 力扣（LeetCode）
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
题目分析：
两个数组，自然就需要考虑二维dp数组了。需要注意的是子数组需要连续，而序列不需要连续。
dp[i][j]:表示0-i的num1和0-j的num2的最长重复子数组为dp[i,j]
递推公式：dp[i][j] = dp[i - 1][j - 1] + 1;
初始化：根据定义需要对第一行和第一列进行初始化，相同值初始化为1.可以画图看看。
public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
//表示0-i的num1和0-j的num2的最长重复子数组为dp[i,j]
int[,] dp=new int[nums1.Length,nums2.Length];
for(int i=0;i<nums1.Length;i++){//初始化第一列
if(nums1[i]==nums2[0]) dp[i,0]=1;
}
for(int i=0;i<nums2.Length;i++){//初始化第一行
if(nums2[i]==nums1[0]) dp[0,i]=1;
}
int res=0;
for(int i=0;i<nums1.Length;i++){
for(int j=0;j<nums2.Length;j++){
if(nums1[i]==nums2[j]&&i>0&&j>0){
dp[i,j]=dp[i-1,j-1]+1;
}
res=Math.Max(res,dp[i,j]);
}
}
return res;
}
}其实，dp数组的含义也可以表示为0-（i-1）的num1和0-（j-1）的num2的最长重复子数组为dp[i,j]
这样表示的话，就不需要对第一行和第一列进行额外的初始化，不过遍历时i和j需要从1开始。
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)