(32)Go贪心算法和动态规划

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

在一个动态规划问题中，设贪心算法为A，最优算法为O，若A能替代O，且不影响求出最优解，就说该问题满足贪心选择性质，此时用贪心算法替代最优算法速度会快很多。

举两例说明：

例1：饼干分配  //

贪心算法：最大的的饼干分给能满足的最贪心的朋友

func findContentChildren(g []int, s []int) int {
    sort.Ints(g) //内部用快速排序实现,升序
    sort.Ints(s)

    n1 := len(g)
    n2 := len(s)
    if n1 == 0 || n2 == 0 {
        return 0
    }

    n1--
    n2--
    count := 0
    for n1 >= 0 && n2 >= 0 {
        if s[n2] >= g[n1] {
            count++
            n1--
            n2--
        } else { //s[n2]<g[n1]
            n1--
        }
    }
    return count
}

例2：无重叠区间 //

解法1：暴力解法，找出所有子区间的集合，之后判断他们不重叠O((2^n)*n)

解法2：动态规划，思路类似求最长上升子序列，需要先对区间排序，之后方便判断不重叠

// 时间复杂度O(n^2),空间复杂度O(n)
func max(v1, v2 int) int {
    if v1 > v2 {
        return v1
    }
    return v2
}

type ints [][]int
// 排序方法(升序),按区间头部排序
func (s ints) Len() int           { return len(s) }
// 区间头部比较
func (s ints) Less(i, j int) bool { return s[i][0] < s[j][0] } 
func (s ints) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }

    // 排序接口
    sort.Sort(ints(intervals))

    // [0...index]包含index的最长不重合区间
    memo := make([]int, n)
    memo[0] = 1
    res := 1
    for i := 1; i < n; i++ {
        memo[i] = 1
        for j := 0; j < i; j++ {
            // 区间头部大于等于另一区间的尾部,即不重合
            if intervals[i][0] >= intervals[j][1] {
                memo[i] = max(memo[i], 1+memo[j])
            }
        }
        res = max(res, memo[i])
    }
    // 区间长度减去最长不重合子区间长度,为需要删除的区间
    return n - res
}

解法3：贪心算法，每次选择最早的，和前一个区间不重合的区间
// 时间复杂度O(n),空间复杂度O(1)
type ints2 [][]int

// 排序方法(升序):按区间尾部排序
func (s ints2) Len() int           { return len(s) }
// 区间尾部比较
func (s ints2) Less(i, j int) bool { return s[i][1] < s[j][1] }
func (s ints2) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func eraseOverlapIntervals2(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }

    // 排序接口,按照结尾升序,因此下一个[]int的结尾肯定大于上一个的结尾
    // 按照这逻辑每次只需跟前面最大能连接在一起的结尾比较即可
    sort.Sort(ints2(intervals))

    endI := intervals[0][1] // 最长不重合区间尾部
    res := 1
    for i := 1; i < n; i++ {
        if intervals[i][0] >= endI {
            res++                  // 最长长度+1
            endI = intervals[i][1] // 更新最长不重合区间尾部值
        }
    }
    return n - res
}

解法1和解法2提交leetcode，通过，由执行用时可以看出，当一个动态规划问题满足贪心选择性质后，用贪心算法优化，性能提升很明显

总结： //
1）贪心选择性质: 在求解一组最优化问题中,使用贪心的方式选择一组内容后,
不会影响剩下的子问题的求解----难度在于判断1个问题是否满足贪心选择性质
2）动态规划问题满足贪心选择性质后,用贪心算法解决性能提升明显
3）如果无法满足贪心性质,举出反例即可，证明贪心选择性质一般用反证法

有bug欢迎指出

最后编辑于：2020.09.07 17:42:53