[代码随想录]Day45-动态规划part13

题目：300. 最长递增子序列

思路：

dp[i]状态 取决于 dp[0] - dp[i-1]中小于dp[i]的元素中最大的值+1，即:

for j:=0; j <i; j++ {
    if nums[i] > nums[j]{
        dp[i] = max(dp[i], dp[j] + 1)
    }
}

代码：

动态规划

func lengthOfLIS(nums []int) int {
    lens := len(nums)
    dp := make([]int, lens)
    for i := 0; i < lens; i++ {
        dp[i] = 1
    }
    res := dp[0]
    for i := 1; i < lens; i++ {
        for j:=0; j <i; j++ {
            if nums[i] > nums[j]{
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}
func max(a,b int)int{
    if a > b {
        return a
    }
    return b
}

参考：

代码随想录

题目：674. 最长连续递增序列

思路：

这题没啥好说的，只取决于前一项的状态；用贪心也可以

代码：

func findLengthOfLCIS(nums []int) int {
    lens := len(nums)
    if lens == 0 {
        return 0
    }
    dp := make([]int, lens)
    for i := 0; i < lens; i++ {
        dp[i] = 1
    }
    res := dp[0]
    for i := 1; i < lens; i++ {
        if nums[i] > nums[i-1] {
            dp[i] = dp[i-1] + 1
        }
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

参考：

代码随想录

题目：718. 最长重复子数组

思路：

如果相等了，状态取决于i-1,j-1

代码：

func findLength(nums1 []int, nums2 []int) int {
    lens1 := len(nums1)
    lens2 := len(nums2)
    dp := make([][]int, lens1 + 1)
    for i := range dp {
        dp[i] = make([]int, lens2 + 1)
    }
    res := dp[0][0]
    for i := 1; i <= lens1; i++ {
        for j := 1; j <= lens2; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            if dp[i][j] > res {
                res = dp[i][j]
            }
        }
    }
    return res
}

参考：

代码随想录