R语言实现动态规划

杀杀

在生信中，动态规划的原理是实现序列比对算法的基础原理之一

经典案例之一就是小偷问题：假如一个小偷需要偷窃连续的十家人，每个屋子里能够偷窃的钱数不同，但是小偷不能连续进入相邻的两间房屋，否则会被发现，小偷需要如何规划自己的偷盗路线才能偷到最多的钱呢

可以把这个问题变形成道德一点的摘苹果问题>o<
假如一天晚上你需要在一条马路上摘苹果，路上有16棵树
树上苹果的数量分别是：
2,7,9,3,1,2,4,2,1,2,5,6,3,6,8,2 个
你不可以连续摘取相邻的两棵树，否则树会报警

那么你要如何才能摘到最多的苹果呢？

简化一下问题，如果路上只有一棵树，你只需要摘取树上的全部苹果
若路上有两棵树，那么他们必然是相邻的，你不能连续摘取他们，因此你应该摘取苹果较多的那棵树上的全部苹果
若路上有三棵树，那么情况分为两种

1. 如果我们摘了第三棵树上的苹果，就必然没有摘取第2棵（3-1相邻）树上的苹果，所以小偷能偷到的苹果是3+max(1到3-2)
2. 如果我们摘了第二棵树，没有摘第三棵也就是最后一棵，我们能摘到的苹果就是max(3-1)。
   三棵树的情况十分简单，无非就是比较<第二棵树>和<第一+第三棵树>的总和大小

如果大于三棵树，此时有n棵树，同理
如果我们摘取了第n棵，那么我们能偷到的最多苹果为n+max(1到n-2)
如果我们没有摘取第n棵，那么能偷到的是max(n-1)

这样递推回去，我们就能得到我们能够摘取的最多苹果树
用python实现这个算法十分常见，我感觉python有很强的递归思想
同样有用C语言和C++实现这个算法，这边使用较少出现的R语言实现以下这个动态规划的理念

#function 写成函数的形式
pick_apple <- function(apple_tree)
{
nums <- apple_tree
data <- array(NA,dim = c(length(nums),2))
data[1,1] <- 0
data[1,2] <- nums[1]
for(i in (2:length(nums)))
{
data[i,1] <- max(data[i-1,1],data[i-1,2]) #Recursion
data[i,2] <- data[i-1,1] + nums[i]
}
return(max(data[length(nums),1],data[length(nums),2]))
}

把题目中的苹果树输入成数组导入函数

tree_test <- array(c(2,7,9,3,1,2,4,2,1,2,5,6,3,6,8,2)) 
#input the number of apples of each tree
pick_apple(tree_test) ##运行函数

大家可以自己尝试一下