对动态规划和递归的理解

动态规划的出身

我们知道，一个可以被数学上递归表示的问题，也可以表示成一个递归算法，在许多情形下对朴素的穷举搜索得到显著的性能改进。
任何数学递归公式都可以直接翻译成递归算法，但是基本现实是，编译器常常不能正确对待递归算法，结果导致递归算法的效率低下。当我们怀疑很可能是这种情况时，我们必须再给编译器提供一些帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统的记录在一个表内，这就是动态规划出现的原因和本质

例子：计算斐波那契数的自然递归程序是非常低效的。
对于递归计算斐波那契数的算法：

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

运行时间T（n）满足T（n）>T（n-1）+T（n-2）。由于T（n）作为斐波那契数满足同样的递归关系并且具有同样的初始条件，因此，事实上T(n)是以斐波那契数相同的速度在增长，从而是指数级的在增长。

其实，计算F（n）所需要的只是F(n-1)和F(n-2)，因此我们只需要记录最近算出的那两个斐波那契数。于是就有了下面的算法：

func Fib2(n int)int{
    if n <= 1{
        return 1
    }
    var ind1,ind2 = 1
    res = 0
    for(i:=2;i<=n;i++){
        res = ind1 + ind2
        ind1 = ind2
        ind2 = res
    } 
    return res
}

递归算法如此慢的原因在于：算法模仿了递归。为了计算Fn，存在一个对F(n-1)和F(n-2)的调用。然而，F(n-1)又递归的对F(n-2)和F(n-3)进行调用，我们就发现存在两个重复的F(n-2)调用。如果探试整个算法，那么我们可以发现，F(n-3)被计算了3次，F(n-4)计算了5次，F(n-5)计算了8次。。。。如图：

image.png
从图中可以看到，f4，f3，f2等都被重复计算了好多次。
冗余计算的增长是爆炸性的。如果编译器的递归模拟算法要是能够保留一个预先算出的值的表，而对已经解过的子问题不再进行递归调用，那么这种指数级的爆炸增长就可以避免。

另外一个例子：

image.png

计算此值的结果(递归实现)：

func getC(n int) float64 {
    if n == 0 {
        return 0
    }

    res := 0.0
    for i := 1; i < n; i++ {
        res += getC(i)
    }
    return 2.0/float64(n)*res + float64(n)
}

func main() {
    res := getC(3)
    fmt.Println(res)
}

非递归实现(借助了表C)：

func getC2(n int) float64 {
    if n <= 0 {
        return 0.0
    }
    c := []float64{0.0}
    sumC := 0.0
    for i := 1; i <= n; i++ {
        sumC = sumC + c[i-1]
        c = append(c, 2.0/float64(i)*sumC+float64(i))
    }
    return c[n]
}

这样时间复杂度就是o(n)，大大提高了效率

//运行getC2(3)时得到的结果：
C:\Users\minping\Desktop>go run 1.go
5.666666666666666

下面我们再考虑一个问题：矩阵乘法的顺序安排
设给定四个矩阵A,B,C,D,A的维度是5010，B的维度是1040，C的维度是4030，D的维度是305。计算ABC*D的结果。虽然矩阵乘法运算是不可交换的，但它是可结合的。。。(这个问题回来再看)

最优二叉查找树

另外一个动态规划的例子：考虑

reference