动态规划的算法

动态规划可以解决很多问题，请设计以下问题的求解方法： 1、写出递归式子 2、递归结束条件 3、编程求出实例的结果。 4、总结一下你知道的可以用动态规划求解的问题，简要说明每个问题递归的子问题空间。 问题1、火柴棍游戏：2堆火柴棍，2人轮流拿。拿的规则如下：1、每次至少拿一根；2、只能从一堆里拿；3、第一堆火柴棍最多拿3根；4、第二堆火柴棍最多拿当前所有火柴棍的一半。谁拿完以后只剩一根火柴棍为赢家。问开始2堆都是20根火柴棍，你想赢，你先拿还是后拿？