动态规划

发表于

菲波那切数列

以斐波那契数列为例，解法有两种-递归和动态规划，动态规划的方法更优。

为什么说动态规划解法更优秀呢？
递归的解法会碰到一个问题(overlap sub-problem重叠子问题)，这就使得每一个f(n)都需要从头递归到最后，其中存在大量的重复计算，利用动态规划的方法可以规避这些额外运算，降低时间复杂度

递归遍历斐波那契额数列时间复杂度是O(2^n) 回想一下一个满二叉树的全部结点公式(2^n-1)
通过动态规划方式时间复杂度为O(n) (其中借助了记忆化搜索)

20190526155888011755260.png

典型题型

最大值/最优解

通常该类题目可用“选和不选”这种方法来解决

例题1

目前有8个任务，同时只能执行一个任务，任务间可能存在时间冲突，每个任务完成后有相应收益，求怎样才能挣最多的钱，是多少？
20190526155888020341492.png

例2

20190526155888045334920.png
有以上一组数字，从中取出一组数字，该组数字两两不相邻，其最大值是多少？

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
41
42
43
44
45
46
47
48
49
50
51
这是一个求最大值最优解的问题，设数组为arr,位置i位置的最优解函数是opt(i)，以选和不选为条件划分
选: arr[i]+opt[i-2]
不选:opt[i-1]
出口:
    opt[0] = arr[0]
    opt[1] = max(arr[0],arr[1])
实现有递归和动态规划两种方式，分别为rec_func和dp_func
*/
func main() {
    in := []int{1, 2, 4, 1, 7, 8, 3}
    //fmt.Println(rec(in, len(in)-1))
    fmt.Println(dp(in))
}
//时间复杂度O(2^n)
func rec(s []int, i int) int {
    if i == 0 {
        return s[0]
    } else if i == 1 {
        return util.Max(s[0], s[1])
    } else {
        a := s[i] + rec(s, i-2)
        b := rec(s, i-1)
        return util.Max(a, b)
    }
}
//时间复杂度O(n)
func dp(arr []int) int {
    opt := make(map[int]int)
    l := len(arr)
    if l == 0 {
        return 0
    } else if l == 1 {
        return arr[0]
    } else if l == 2 {
        return util.Max(arr[1], arr[0])
    } else {
        opt[0] = arr[0]
        opt[1] = Max(arr[1], arr[0])
        for i := 2; i < l; i++ {
            a := arr[i] + opt[i-2]
            b := opt[i-1]
            opt[i] = util.Max(a, b)
        }
        return opt[l-1]
    }
}

例3

给定一组数，从中抓取任意数量的数字，使其和为s，如果存在这种情况，返回true，不存在返回false

arr={3,34,4,12,5,2}
s=9

思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1.先找出状态转移关系
用subset来表示子集 subset(i，s) 其中i表示前i个数字，s为最终要加出来的数字
根据是否选取第i个数字做判断:
    subset(i-1,s-arr[i])     选取第i个数字，那么问题转化为剩下的子集值是否等于s-arr[i]
    subset(i-1，s)           不选取第i个数字，问题转化为剩下的子集是否等于s
2.接下来找出口
当s==0时，已经满足条件，return true
当i==0时，return s==arr[0]
当arr[i]>s时，return subset(arr,i-1,s)  //剪枝
其他
    A=subset(arr,i-1,s-arr[i])
    B=subset(arr,i-1,s)
    return A or B
3.使用dp方式 使用数组记录中间状态(备忘录)
因为有i,s两个变化的量，备忘录是二维数组
![20190528155905164782497.png](http://pic.aipp.vip/20190528155905164782497.png)
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//递归方法
func rec_subset(arr []int,i int,s int)bool{
    if s==0{
        return true
    }else if i==0 {
        return s==arr[0]
    }else if arr[i]>s{
        return rec_subset(arr,i-1,s)
    }else{
        a:=rec_subset(arr,i-1,s-arr[i])
        b:=rec_subset(arr,i-1,s)
        return a || b
    }
}
//dp方法
func dp_subset(arr []int, i int, s int) bool {
    //初始化备忘录数组 包括s==0 和 s==arr[i]的情况
    sub := [][]bool{}
    for j := 0; j < len(arr); j++ {
        l := make([]bool, s+1)
        for k := 0; k < s; k++ {
            if k == 0 {
                l[k] = true
            } else {
                if j == 0 && arr[j] == k {
                    l[k] = true
                }
            }
        }
        sub = append(sub, l)
    }
    //i和s都从1开始遍历
    for j := 1; j < len(arr); j++ {
        for k := 1; k <= s; k++ {
            if arr[j] > k {
                sub[j][k] = sub[j-1][k]
            } else {
                a := sub[j-1][k]
                b := sub[j-1][k-arr[j]]
                sub[j][k] = a || b
            }
        }
    }
    return sub[len(arr)-1][s]
}
a := []int{3, 34, 4, 12, 5, 2}
fmt.Println(dp_subset(a, len(a)-1, 9))
fmt.Println(dp_subset(a, len(a)-1, 10))
fmt.Println(dp_subset(a, len(a)-1, 11))
fmt.Println(dp_subset(a, len(a)-1, 12))
fmt.Println(dp_subset(a, len(a)-1, 13))
true
true
true
true
false

例4

你需要爬一个n阶台阶，每次可以向上走1至2步，那么n阶台阶有多少种走法呢？（leetcode）

例5

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

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
41
42
43
44
45
46
47
48
49
50
51
/**
思考:
1.寻找状态转移变量
设f(n) 是到第n天时的最大收益
对于第i天
    如果卖出，最大收益为prices[i]-minprice(i-1)      //minprice为前i-1天中最低价格
    如果不卖出，最大收益为f(i-1)
故第i天最大收益收益为Max(prices[i]-minprice(i-1),f(i-1))
2.找出口(初始值)
f(0) = 0
minprice(0) = prices[0]
3.使用dp方式通过minprice切片做备忘录
4.优化
f(i)与f(i-1)有关 对于备忘录可以只保存每次迭代时的前一个f值，定义为maxprofit
minprice(i)与minprice(i-1)有关同样也可只保存前一个值，定义为minprice
**/
func maxProfit(prices []int) int {
    if len(prices)==0{
        return 0
    }
    minprice:=prices[0]
    maxprofit := 0
    for i:=1;i<len(prices);i++{
        maxprofit = Max(prices[i]-minprice,maxprofit)
        minprice = Min(minprice,prices[i])
    }
    return maxprofit
}
func Max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}
func Min(a,b int)int{
    if a<b{
        return a
    }else{
        return b
    }
}

参考资料

动态规划1
动态规划2

动态规划一般写成非递归形式
动态规划和递归的关系是什么？动态规划属于思想，递归是动态规划实现的一种方式吗？
建立备忘录的迭代就是动态规划
动态规划自底向上

递归 一定要有递归出口 参见递归
出口条件

记忆化搜索

爬楼梯
背包

overlap sub-problem
重叠子问题

剪枝 去掉不需要的情况

subset