hdu 2018 母牛的故事 (基础dp,记忆化搜索)

hdu2018题目链接

题意:第1年有1头奶牛,每年生一头奶牛,新生的奶牛从生下来的第四年(包括生下来那年)也开始每年一头奶牛。
问第n年有多少头奶牛。
思路:最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4)

递推代码:

 

也可以考虑记忆化嘛

理论上应该是所有的dp都可以写成记忆化。。。?

记忆化的好处是不用考虑什么边界的问题。。。坏处是。。可能爆栈。。。。。

 

记忆化代码:

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz