动态规划算法 - Thu, Jun 11, 2020

动态规划算法

1. 概述

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

2. 示例

斐波那契数列是动态规划最好的示例

暴力递归

func fib(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	return fib(n-1) + fib(n-2)
}

保存子问题值

var tmp = map[int]int{}

func fib(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	value, ok := tmp[n]
	if ok {
		return value
	}
	value = fib(n-1) + fib(n-2)
	tmp[n] = value
	return value
}

从底到上

func fib(n int) int {
	var tmp = map[int]int{}
	tmp[1], tmp[2] = 1, 1
	for i := 3; i <= n; i++ {
		tmp[i] = tmp[i-1] + tmp[i-2]
	}
	return tmp[n]
}

从底到上优化空间复杂度

func fib(n int) int {
	a, b := 1, 1
	for i := 3; i <= n; i++ {
		b, a = a+b, b
	}
	return b
}