写了一个dp.fus

[dou4cc]

dp.fus：

0.5.0

export: f->
  cache: new Map()
  arg->
    if cache.has arg then
      cache.get arg
    |
      result: f arg
      cache.set(arg, result)
      result

示例：

0.5.0

import "./dp.fus" as dp

count: dp n->
  if n=1 or n=2 then
    1
  |
    count(n-1)+count(n-2) #斐波纳契数列

console.log count 1 #1
console.log count 2 #1
console.log count 3 #2
console.log count 4 #3
console.log count 5 #5
console.log count 6 #8
console.log count 7 #13
console.log count 8 #21
console.log count 9 #34

[XGHeaven]

你确定这是dp，明明是dfs好不好 :angry:

[dou4cc]

@XGHeaven 动态规划的基本原理是给递归函数加缓存，有错吗？

[XGHeaven]

@dou4cc 不对吧。动态规划的基本原理可不是递归函数加缓存这么简单。你知道dp，你应该懂，首先要有状态转移方程的。。d[i] = d[i-1] + d[i-2]，我并不觉得这是一个dp，其实我只是觉得这么简单的东西，明明就是dfs+缓存优化，你非要说成dp，至于么 :joy: 。至于这个到底属不属于dp的范畴，已经两年没碰过oi了，我也忘了。

[dou4cc]

@XGHeaven 见《算法导论（原书第3版）》第207页：“第一种方法称为带备忘的自顶向下法(top-down with memoization)。”

[dou4cc]

@XGHeaven 见《算法导论（原书第3版）》第207页：“如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡(time-memory trade-off)的例子。”

[XGHeaven]

首先，你看过算法导论，不错不错。

不过我想跟你说，dp通常是求解最优解问题，也就是说会有多个子问题，从中选择一个。但是你这个求解fib没有什么最优解。如果你说，每个问题都有一个子问题，那么不也是dp么。对没错，但是你不觉得这太牵强了么。就相当于你拿到一个一元一次方程，你说他是一元二次方程组，就是二次项为0了呀，你觉得合适么。

我并不是质疑dp的概念，我只是说，你说dp不太准确。说成求解fib或者用dfs优化的方式求解fib都可以。但是你直接说dp，这有有点你在炫耀自己学的多的感觉了。

[dou4cc]

@XGHeaven 斐波那契数列不是动态规划中的Hello World吗？我学动态规划就是从这个例子入门的啊~

[XGHeaven]

我擦，我当初学的时候，可不是这个入门的。 :joy: 好吧，那这就不怪你了。

[XGHeaven]

抱歉

[dou4cc]

:)

[XGHeaven]

既然书上都这么说，我就真的没办法了。虽然我还是觉得他不算一个严格意义上的dp