• 动态规划示例理解

    动态规划

    为什么有这个话题，由一个问题而来

    问题

    给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

    • answer[i] % answer[j] == 0 ，或

    • answer[j] % answer[i] == 0

      如果存在多个有效解子集，返回其中任何一个均可。

    示例 1：

    输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

    • 1
    • 2
    • 3

    示例 2：

    输入：nums = [1,2,4,8]
输出：[1,2,4,8]

    • 1
    • 2

    我的解答

    思路一

    先找出有倍数关系的结果，然后找出能除尽有倍数关系的每一个元素，如果结果是每一个元素的倍数，那么把这个结果添加到结果中，这样这个列表会越来越长，看是否能得到最终的结果

    func largestDivisibleSubset(nums []int) []int {
    var answer []int
    ins := false
OuterLoop:
    for i:=0;i<len(nums);i++{
        for j:=i+1;j<len(nums);j++{
            if nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0{
                answer = append(answer, nums[i], nums[j])
                ins = true
                break OuterLoop;
            }
        }
    }
    if ins{
        for _,num := range nums{
            ok := true
            for _,ans := range answer{
                if num % ans != 0{
                    ok = false
                    break
                }
            }
            if ok{
                in := false
                for _,obj := range answer{
                    if num == obj{
                        in = true
                    }
                }
                if !in{
                    answer = append(answer,num)
                }
            }
        }
    }
    if len(answer) == 0 && len(nums) >= 0{
        answer = []int{nums[0]}
    }
    return answer
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    结果：21 / 48 个通过测试用例

    输入
[3,4,16,8]
输出
[4,16]
预期结果
[4,8,16]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    思路二

    既然要求最大长度的整除子集，那么就先将它排序，排序后计算首位的倍数，假订首位一定是因数。

    func largestDivisibleSubset(nums []int) []int {
    for i := 1;i<len(nums);i++{
      tmpv := nums[i]
      j := i-1
      for ;j >= 0 && nums[j] > tmpv;j--{
          nums[j+1] = nums[j]
      }
      nums[j+1] = tmpv
    }
    if len(nums) <= 1{
        return nums
    }
    answer := []int{nums[0]}
    for _,num := range nums[1:len(nums)]{
        ok := true
        for _,ans := range answer{
            if num % ans != 0{
                ok = false
                break
            }
        }
        if ok{
            answer = append(answer, num)
        }
    }
    return answer
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    结果：34 / 48 个通过测试用例

    输入
[3,4,16,8]
输出
[3]
预期结果
[4,8,16]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    思路三

    既然最小的数不一定是因子，那么就枚举每一个对象，假订每一个数都可能是最小因子，然后选出最优

    func largestDivisibleSubset(nums []int) []int {
    for i := 1;i<len(nums);i++{
      tmpv := nums[i]
      j := i-1
      for ;j >= 0 && nums[j] > tmpv;j--{
          nums[j+1] = nums[j]
      }
      nums[j+1] = tmpv
    }
    if len(nums) <= 1{
        return nums
    }
    var res []int
    for i:=0;i<len(nums);i++{
        answer := []int{nums[i]}
        for j:=i+1;j<len(nums);j++{
            ok := true
            for _,ans := range answer{
                if nums[j] % ans != 0{
                    ok = false
                    break
                }
            }
            if ok{
                answer = append(answer, nums[j])
            }
        }
        if len(answer) > len(res){
            res = answer
        }
    }

    return res
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    结果：39 / 48 个通过测试用例

    输入
[5,9,18,54,108,540,90,180,360,720]
输出
[5,90,180,360,720]
预期结果
[9,18,90,180,360,720] //枚举到9时，命中了[9,18,54,108,540],和结果一样长

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    思路四

    既然有可能是跳过某个对象的，那么排序就没有用呀，不如直接枚举每个对象为可能是最小公因数，然后找出最长的，当相等时，不加入到最优的列表

    func largestDivisibleSubset(nums []int) []int {
    if len(nums) <= 1{
        return nums
    }
    var arr []int
    for i:=0;i<len(nums);i++{
        obj := []int{nums[i]}
        fmt.Println("---",obj)
        for j:=0;j<len(nums);j++{
            ok := true
            for _,ans := range obj {
                if ans % nums[j] != 0 && nums[j] % ans != 0{
                    ok = false
                    break
                } 
            }
            if ok && nums[j] != obj[0]{
                obj = append(obj, nums[j])
            }
        }
        if len(obj)>len(arr){
            arr = obj
        }
    }
    for i := 1;i<len(arr);i++{
      tmpv := arr[i]
      fmt.Println(arr[i])
      j := i-1
      for ;j >= 0 && arr[j] > tmpv;j--{
          arr[j+1] = arr[j]
      }
      arr[j+1] = tmpv
	}

    return arr
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    结果：43 / 48 个通过测试用例

    输入
[5,9,18,54,108,540,90,180,360,720]
输出
[9,18,54,108,540]
预期结果
[9,18,90,180,360,720]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    思路五

    看没有通过的测试用例，如果从最大开始找，那么是可以将最长记录找出来的

    func sortArr(nums []int)[]int{
   for i := 1;i<len(nums);i++{
		tmpv := nums[i]
		j := i-1
		for ;j >= 0 && nums[j] > tmpv;j--{
		    nums[j+1] = nums[j]
		}
		nums[j+1] = tmpv
	}
    return nums
}

func largestDivisibleSubset(nums []int) []int {
    if len(nums) <= 1{
        return nums
    }
    nums = sortArr(nums)
    var arr []int
    for i:=len(nums)-1;i>-1;i--{
        ins := nums[i]
        answer := []int{ins}
        for j:=i-1;j > -1;j--{
            if ins % nums[j] == 0{
                answer = append(answer, nums[j])
                ins = nums[j]
            }
        }
        fmt.Println(sortArr(answer))
        if len(arr) < len(answer){
            arr = answer
        }
    }
    return sortArr(arr)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    结果：45 / 48 个通过测试用例

    输入
[4,8,10,240]
输出
[10,240]
预期结果
[4,8,240]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    总结

    总结一下，到这里，以上所有的思路，都不会得到最终结果，因枚举到某个对象时，他可能的因数可能会跳过比当前数小的值，最长的可能是比之次小的因数，所以枚举一种的前提下是有可能由多种情况的，但是这个情况用暴力的方式很难解决，以**[4,8,10,240]**为例，会有以下枚举树，代码实现不确定的树形，不好实现，所有这种思路感觉也不可取

    在这里插入图片描述

    动态规划（dynamic programming）

    Simplifying a complicated problem by breaking it down into simpler sub-problems

    动态规划常常适用于分治和最优子结构性质的问题

    动态规划与递归

    动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）

    共性：找到重复子问题

    差异性：动态规划是最优子结构，中途可以淘汰次优解

    动态规划是自底向上，递归是自顶向下

    啥叫「自顶向下」？

    注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」

    func fibo(n int)int{
  if n<=1{
    return n
  }
  return fibo(n-1)+fibo(n-2)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    啥叫「自底向上」？

    反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

    func fibo(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    Count the paths

    黄色框是障碍物，只能向右或者向下走，有多少种走法？

    递归

    在这里插入图片描述

    dp递推

    在这里插入图片描述

    dp递推结果

    在这里插入图片描述
    在这里插入图片描述

    最终解答

    在这里插入图片描述

    func largestDivisibleSubset(nums []int) (res []int) {
    sort.Ints(nums)

    // 第 1 步：动态规划找出最大子集的个数、最大子集中的最大整数
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    maxSize, maxVal := 1, 1
    for i := 1; i < n; i++ {
        for j, v := range nums[:i] {
            if nums[i]%v == 0 && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > maxSize {
            maxSize, maxVal = dp[i], nums[i]
        }
    }

    if maxSize == 1 {
        return []int{nums[0]}
    }

    // 第 2 步：倒推获得最大子集
    for i := n - 1; i >= 0 && maxSize > 0; i-- {
        if dp[i] == maxSize && maxVal%nums[i] == 0 {
            res = append(res, nums[i])
            maxVal = nums[i]
            maxSize--
        }
    }
    return
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
  • 相关阅读:
    【机器学习】02. 使用sklearn库牛顿化、正则化的逻辑回归（代码简洁，思路推导）
    Geoffrey Hinton：深度学习的下一个大事件
    解决AnyViewer干扰控制端输入法的问题
    法大大携手企企科技，助力企业实现全生命周期合同管理
    SQL 基础知识梳理（一）- 数据库与 SQL
    Android Studio设置
    微服务组件--注册中心Spring Cloud Eureka分析
    系列三、创建线程的方式
    Fhopify：跨境电商行业迎来发展新机遇打造购物者天堂
    前端工程化-基于Taro的Web端Monorepo架构改造
  • 原文地址：https://blog.csdn.net/weixin_43568060/article/details/126364539