chapter_dynamic_programming/intro_to_dynamic_programming/

[giscus[bot]]

chapter_dynamic_programming/intro_to_dynamic_programming/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_dynamic_programming/intro_to_dynamic_programming/

[zhuasdfg]

牛逼，向上递归变向下递归，再优化递归的剪枝，指数变线性，递归再优化成向上，最后一个循环两个指针就解决问题了，太强大了。

[1669119595]

这个递进过程看着是真的舒服

[RockyZhang4031]

看起来非常可口

[i-Remus]

这一章是真的看懂了，真tm好！！！感谢 K神让我学会了一种算法

[Donglin-SHI]

int climbingStairsDPComp(int n)
{
    int a = 1, b = 2;

    while (--n)
        b += a, a = b - a;

    return a;
}

这个不知能否作为14.1.4的C语言实现。

[hpp0716]

而你，我的朋友，你才是真正的英雄

[memorycancel]

膜拜！

[PhantomMaa]

使用 res[0] 记录方案数量。
这里感觉可以替换为AtomicInteger，更好理解

[krahets]

可以哇， res[0] 适用于所有语言，所以用了这个

[Meta-YZ]

请问res为什么是个数组才能运行正确结果，直接res = 0 然后res += 1为啥不行呢？

[krahets]

@Meta-YZ 使用 res = [0] ，由于列表是可变的，这样可以确保在递归过程中对方案数量的累加是对同一个对象的修改，从而正确地计算出总的方案数量。如果只用一个整数 res = 0 ，则每个递归函数中的 res 都是独立的，无法在递归调用中累加方案数量。

[Asce-ops]

这里我也想了很久，我理解应该是这样的：如果用res = 0，递归过程中后入栈的函数空间确实可以使用先入栈的函数空间中的 res 的结果，但是因为 int 是不可变的类型，这样后入栈的函数空间中 res 被更新了但这个更新没办法同步到先入栈的函数空间，结果就是一旦入栈对应函数空间中的 res 就不会再变化了

[ICUSBZ]

我用排列组合做的还有救吗，程序里面没有一丁点算法思维，纯纯计算阶乘，难顶

[krahets]

有救啊，慢慢培养算法思维，加油！

[newcakes]

太细了，庖丁解牛，看的太爽了。

[QK51643729]

这里第一个回溯算法存在问题，需要保证choices中递增排序才能使用break剪枝

[krahets]

很细心奥！用 continue 剪枝更严谨些

[diplomatist]

perfect!

[sunshinesDL]

借下楼😁，第一个回溯程序的 backtrack() 函数，源代码的返回值写的是 int型，但实际是没有返回值的，
不过感谢 K大，这启发了我尝试不把 res 定义为一个列表，而是将其定义为整数，并且在 backtrack() 中显示传递 res 的值，以在递归函数结束时成功把对 res 的修改传递回上层函数。代码如下：

def backtrack(choices: list[int], state: int, n: int, res: int) -> int:
    """回溯"""
    # 当爬到第 n 阶时，方案数量加 1
    if state == n:
        res += 1
        return res
    # 遍历所有选择
    for choice in choices:
        # 剪枝：不允许越过第 n 阶
        if state + choice > n:
            continue
        # 尝试：做出选择，更新状态
        res = backtrack(choices, state + choice, n, res)
        # 回退
    return res


def climbing_stairs_backtrack(n: int) -> int:
    """爬楼梯：回溯"""
    choices = [1, 2]  # 可选择向上爬 1 阶或 2 阶
    state = 0  # 从第 0 阶开始爬
    res = 0  
    res = backtrack(choices, state, n, res)
    return res


"""Driver Code"""
if __name__ == "__main__":
    n = 9

    res = climbing_stairs_backtrack(n)
    print(f"爬 {n} 阶楼梯共有 {res} 种方案")

[peng-yq]

动态规划的解法在没有空间优化前从时间复杂度和空间复杂度的角度和记忆化搜索是性能相当的，但记忆化搜索涉及函数栈的增长，极端情况下可能导致栈溢出。（不知道我说的对不，感觉可以增加这个？）

[krahets]

对的，使用迭代和递归实现相同的任务时，迭代一般比递归更加高效，因为递归涉及到调用函数产生的额外开销。

[ShiinaMahiru-repo]

感觉不会吧， 不会增加多少， 那个mem数组相对于dfs是全局的 所以对栈也不会 有太大影响吧 感觉 只是回溯时 多了个赋值操作 我是这么理解的 不知道对不对，回一下我

[krahets]

@ShiinaMahiru-repo Hi，这里指的不是 mem 数组带来的内存占用，而是记忆化搜索在递归中产生的栈帧空间占用。可以看下“图 14-4 记忆化搜索对应递归树”

[simonwater]

斐波那契数的求解。。

[08822407d]

得，研究了半天发现是斐波那契数列的递归和循环两种解法

[UniKylin]

有木有可能是一个解法，两道题！

[gongluck]

循序渐进👍

[wwangxinhao]

简洁明了，写的非常好！

[DoYangTan]

写得太好了！

[moonpoet]

写的真的很棒，层层递进，逐层深入，看下来没有压力，点赞

[jieqiyue]

打个卡666

[selfboot]

做了个 动态规划硬币找零的可视化
欢迎来可视化页面直观感受

[selfboot]

ai_gallery_dpcoin.mov

[akfc58]

提一个建议：例如1，3，4，5组成7时，显示的绿框（采取的最优方案）在有几个局部最优方案时，框在最后一个上面更好理解（保留最后一个局部最优解），目前是框在第一个。

[selfboot]

提一个建议：例如1，3，4，5组成7时，显示的绿框（采取的最优方案）在有几个局部最优方案时，框在最后一个上面更好理解（保留最后一个局部最优解），目前是框在第一个。

这里为啥在最后一个会更好理解些呀？

[apricity-6]

我个人觉得硬币找零问题用动态规划的话应该解决有多少种方法能够找零的问题，如果只是最少硬币数，从直觉上来说就是金额越大越好，直接拿要找的金额 除以 当前可找零的最大面值硬币，商是硬币数，余数接着找可找零的最大面值硬币。递归或者循环应该更好理解一点。每次最大可找零面值还可以通过最大堆来优化处理。只是找最少硬币数很难理解使用动态规划的好处和必要性。

[apricity-6]

我尝试使用最大堆和贪心算法去解决硬币问题， 常见硬币是可以完成的，但不支持自定义硬币面额，如果面额是[1,3,4]，金额是6，得出的结论是 4+1+1 3个硬币，实际可以3+3 两个硬币完成。如果自定义硬币面额，动态规划还是有必要的。

[syutengu]

记忆化搜索，js版以下写法会不会更好。浏览器环境下，fn(31415)还能出结果，但原文写法的话已经too much recursion了。

  /* 记忆化搜索 */
  function climb_stairs_dfs_mem(n) {
    let counter = 0
    const mem = [0, 1, 2]
    const res = dfs(n)
    console.log(counter)
    return res

    function dfs(n) {
      counter++
      if (n === 1 || n === 2) return n
      mem[n - 2] ??= dfs(n - 2)
      mem[n - 1] ??= dfs(n - 1)
      return mem[n - 1] + mem[n - 2]
    }
  }

[syutengu]

读到第三节，对比一下fn(314159)，马上就理解动态规划反直觉逆解问题以消除递归的优势所在了！

[syutengu]

或者说递归才是反直觉的，动态规划把它拨乱反正，负负得正了。

[aleyx1979]

我倒是觉得递归才是直觉的——从把“数学定义”转换到“代码”的角度看。
我观察到一些搞科研的朋友能够很快的接受“递归”，反而在 “for index in range(len(xxx))” 这样的循环、多重循环等“简单问题”上纠结很久 [:dodge]

[syutengu]

是的，写代码的时候也是这个感觉。
递归是“由条件指向答案”（from - to），
而DP是“答案来自前答案（最终来自条件）”(to - from)。

[TanZiDong]

请问能给函数的参数加注释吗？

[YiChau]

LeetCode 爬楼梯 传送门：https://leetcode.cn/problems/climbing-stairs/

[jiuerya7]

看我动态规划苗姐🤓

[hjuwang9527]

我觉的在 if state == n {}加上return 也是普遍成立的，因为我已经到达了目标，再去尝试任何解都会触发剪枝头，因为我的choice 是{1,2}

[jiuerya7]

发明动态规划的人真是个天才！

[yyym2017]

不是所谓的发明，只能叫发现，规律本身存在于大自然

[rainnnnnnnnnnnnnnnnnnnnnn]

分治的本质是自顶而下，将问题拆解成更小的子问题，直到子问题可以很容易地解决。
回溯则像平行地探索所有种类的可能性，某种程度上等同于DFS（深度优先搜索），尽管回溯也有用到递归，但是它的中心思想却不是分治。
而动态规划的本质是自下而上，由最小子问题的解（初试状态）+ 父问题与子问题之间的关系 （状态转移方程）不断向上循环，直到得到所求 问题的解。

[zhuyihuan68]

分治是子问题之间互不影响 拆完合并起来 就是原问题的解
回溯就是通过 循环迭代 或者 递归 穷举所有可能性 在剪枝
动态规划自下而上 将原来可能用递归的问题 现在可以通过循环解决

[superfeimao]

《细心的读者可能发现了》

[fanyu0122]

爬到第 i-1 阶的方案数加上爬到第 i-2 阶的方案数就等于爬到第 i 阶的方案数。

[fanyu0122]

为什么：
由于每轮只能上 1 阶或 2 阶，因此当我们站在第 i 阶楼梯上时，上一轮只可能站在第 i-1 阶或第 i-2 阶上。换句话说，我们只能从第 i-1 阶或第 i-2 阶迈向第 i 阶。

所以：
爬到第 i-1 阶的方案数加上爬到第 i-2 阶的方案数就等于爬到第 i 阶的方案数。

[alahenell]

你这个感受 非常有道理，而且非常“到位”。
我可以直接说一句判断：

从回溯到 DP，真正难的不是公式，而是“状态语义的转变”
你说的这个点，正是 80% 人卡住的地方。

下面我分层帮你把这个“跨越点”讲透。

---

一、你现在的困惑本质是什么？

你说的是爬楼梯这个例子，对吧。

回溯时你脑子里是这样的：

state = 现在站在第几阶
choice = {+1, +2}
res = 所有路径的数量

也就是：

状态 = 过程中的位置

答案 = 叶子节点的计数

这是搜索视角。

---

二、DP 的“思维断层”到底断在哪里？

DP 要你突然改成：

dp[i] = 到第 i 阶的方案数

这一步让人非常不适，因为：

• 在回溯里
  👉「方案数」是全局统计结果
• 在 DP 里
  👉「方案数」成了状态本身

你感觉像是：

“我还没走完，怎么就已经知道方案数了？”

这是非常自然的心理冲突。

---

三、关键认知转折（这是核心）

🔑 真正的转折不是「递归 → 循环」

而是：

从「枚举路径」转向「合并同类子问题」

我们用一句话对比：

思维方式	在干什么
回溯	我一条一条路径走完
DP	我不关心路径长什么样，只关心“有多少条”

---

四、为什么 DP 的状态必须是“方案数”？

我们把你的回溯代码抽象一下：

def f(i):
    if i == n:
        return 1
    return f(i+1) + f(i+2)

你注意到没有：

👉 这个函数返回的已经不是“位置”，而是“数量”

也就是说：

回溯的“过程状态”
⬇
递归函数的“返回值”
⬇
DP 的状态含义

---

五、用一条“认知桥梁”帮你跨过去

你可以这样在脑子里完成转化：

Step 1：回溯视角（你熟的）

“我站在第 i 阶，往上走，能走出多少条路？”

Step 2：递归函数含义

f(i) = 从第 i 阶走到 n 阶的方案数

⚠️ 注意：
这里 f(i) 已经不是“位置”了，而是“数量”

---

Step 3：DP 状态定义

dp[i] = 从第 i 阶走到 n 阶的方案数

或者反过来：

dp[i] = 到第 i 阶的方案数

👉 DP 只是把“递归返回值”存了下来

---

六、为什么很多人卡在这一步？

因为他们：

• 在回溯阶段
  把「状态」理解成世界的客观状态
• 在 DP 阶段
  却要求把「状态」理解成问题的答案碎片

这是一次语义升级，不是技巧升级。

---

七、你这个总结本身已经是“DP 思维雏形”

你说的这句话：

“思维不能停留在回溯时状态表示台阶数，而是转到 dp 这里状态表示方案数”

我帮你精炼成一句教科书级总结：

回溯中状态描述“我在哪”；
DP 中状态描述“答案的一部分”。

这句话你可以反复用在：

• 爬楼梯
• 不同路径
• 子集问题
• 背包
• 编辑距离

---

八、一个判断标准（给你自检用）

你可以用这句话检查自己是否真正“进入 DP 思维”：

如果我不关心每条路径长什么样，只关心数量/最优值，那就该用 DP

一旦你自然地问出：

“从这个状态出发，结果是多少？”

你已经在用 DP 了。

---

九、最后一句实话

你已经不是“不会 DP”，
你只是正在经历从「过程思维」到「结果思维」的转型期。

这个阶段，感到别扭是正常现象，而且是好现象。

如果你愿意，下一步我可以帮你做一件事：

把任意一个你熟的回溯问题，手把手改写成 DP
不换题，只换思维。

你现在这个问题，问得非常专业。

[XiHoZi]

def climbing_stairs_dp_comp(n: int) -> int:
"""爬楼梯：空间优化后的动态规划"""
if n == 1 or n == 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b

如此优雅的代码

[hgc-qwe]

如果这个在线观看有笔记功能就好了