动态规划

[TOC]

Leetcode刷题

300. 最长递增子序列【中等】

// ============= 解法一：基本动态规划 =============
func lengthOfLIS(nums []int) int {
   if len(nums) <= 1 {
      return len(nums)
   }
   dp := make([]int, len(nums))
   for i := 0; i < len(nums); i++ {
      dp[i] = 1
   }

   res := 1
   for i := 1; i < len(nums); i++ {
      for j := 0; j < i; j++ {
         if nums[i] > nums[j] {
            dp[i] = max(dp[i], dp[j]+1) // 状态转移方程，如果num[i]>num[j],说明num[j]
            res = max(res, dp[i])
         }
      }
   }

   return res
}

参考网址：
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/xun-xu-jian-jin-dan-diao-zhan-er-fen-cha-d3hf/

//// ======== 解法二： 单调栈 + 二分查找 完美契合  =================
func lengthOfLIS(nums []int) int {
   if len(nums) <= 1 {
      return len(nums)
   }
   stack := []int{nums[0]} // 第一个直接入栈，维护一个单调递减栈

   for i := 1; i < len(nums); i++ {
      if nums[i] > stack[len(stack)-1] { // 当前元素>栈顶元素，直接入栈，栈的单调递减特性没变。
         stack = append(stack, nums[i])
      } else if nums[i] < stack[len(stack)-1] {
         stack = binarySearch_replace(stack, nums[i])
      }
   }
   fmt.Println(stack)
   return len(stack)
}

 
func binarySearch_replace(array []int, target int) []int {
   left, right := 0, len(array)-1
   for left <= right {
      mid := (left + right) / 2
      if array[mid] == target {
         right = mid - 1
      } else if array[mid] > target {
         right = mid - 1
      } else if array[mid] < target {
         left = mid + 1
      }
   }
   array[left] = target
   return array
}