0%

7算法-动态规划

1. 动态规划

看个小故事:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*

"What's that equal to?"

*counting* "Eight!"

*writes down another "1+" on the left*

"What about that?"

*quickly* "Nine!"

"How'd you know it was nine so fast?"

"You just added one more"

"So you didn't need to recount because you remembered there were eight!Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"

按照定义,动态规划是把一个大问题拆解成一堆小问题,这个本身没啥问题,但是我觉得的这个不是动态规划的核心思想,或者说,一个”大问题“之所以能用”动态规划“解决,并不是因为它能拆解成一堆小问题,事实上啥大问题都能拆解成小问题…

取决于该问题是否能用动态规划解决的是这些”小问题“会不会被被重复调用。

2. 算法

2.1 连续子数组的最大和(简单)

  • 动态规划, 用到临时存结果

  • 临时结果, 有前因后果关系, 想想8+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxSubArray(nums []int) int {
dp := make([]int, len(nums))
dp[0] = nums[0]
max := dp[0]
for i := 1; i < len(nums); i++ {
dp[i] = Max(dp[i-1]+nums[i], nums[i])
max = Max(dp[i], max)
}
return max
}

func Max(a, b int) int {
if a < b {
return b
}
return a
}

2.2 青蛙跳台阶问题(简单)

  • 递归超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func numWays(n int) int {
if n <= 1 {
return 1
}
dp := make([]int,n+1)
dp[0]= 1
dp[1]= 1

for i:=2; i <= n; i++{
dp[i] = (dp[i-1] + dp[i-2])%1000000007
}

return dp[n]
}

2.3 斐波那契数列(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func fib(n int) int {
if n <= 1 {
return n
}

f1, f2 := 0, 1
for i := 2; i <= n; i++{
temp := (f1 + f2)%1000000007
f1 = f2
f2 = temp
}

return f2
}

3. 参考资料

给作者打赏,可以加首页微信,咨询作者相关问题!