动态规划

28 Aug 2019 • Fish-pro

通过本文示例，理解动态规划

问题

给你一个由无重复正整数组成的集合 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] 也会被视为正确答案。

示例 2：

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

我的解答

思路一

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

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
}

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

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

思路二

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

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
}

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

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

思路三

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

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
}

结果：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],和结果一样长

思路四

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

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
}

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

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

思路五

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

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)
}

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

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

总结

总结一下，到这里，以上所有的思路，都不会得到最终结果，因枚举到某个对象时，他可能的因数可能会跳过比当前数小的值，最长的可能是比之次小的因数，所以枚举一种的前提下是有可能由多种情况的，但是这个情况用暴力的方式很难解决，以[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)
}

啥叫「自底向上」？

反过来，我们直接从最底下，最简单，问题规模最小的 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]
}

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
}

algorithm