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 都是独立的，无法在递归调用中累加方案数量。

[ICUSBZ]

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

[krahets]

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

[newcakes]

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

[QK51643729]

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

[krahets]

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

[diplomatist]

perfect!

[peng-yq]

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

[krahets]

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

[ShiinaMahiru-repo]

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

[krahets]

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

[wudi-cloud]

斐波那契数的求解。。

[08822407d]

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

[gongluck]

循序渐进👍

[wwangxinhao]

简洁明了，写的非常好！

[DoYangTan]

写得太好了！

[xuejian-git]

质量太高了吧

[ShiinaMahiru-repo]

说起来这个滚动是不是可以这样

1. b = a + b;
   a = b - a;
2. tmp = a;
   a = b;
   b = a + tmp;
3. tmp = b;
   b = a + b;
   a = tmp;

[krahets]

2., 3. 都是正确写法。不推荐 1.，可读性不好，且考虑通常比 2.,3. 更低。1. 适合做脑筋急转弯题

[ShiinaMahiru-repo]

哦， 明白了， 谢谢回复

[ShiinaMahiru-repo]

让我想起了滚动数组

[ahui-5144]

climbing_stairs_backtrack.java
        if (state == n) {
            res.set(0, res.get(0) + 1);
            return;
        }

我试了几个数据,这里加上return后结果没有改变,而且运行速度更快,请问这样子加上return会有什么隐患嘛(作者这里没有加return是有什么考虑嘛)

[krahets]

Hi，这样做主要是为了符合文中的描述“每当到达楼梯顶部时就将方案数量加 1 ，当越过楼梯顶部时就将其剪枝”。
针对这个 case ，加 return 会变的更快（提前返回），没有什么隐患

[coder-yangxin]

举个手🤔

爬楼梯 回溯算法实现中为什么不需要回退操作，这个案例和13章中需要回退的案例有什么区别呢

[hpstory]

Hi @coder-yangxin , 其中一个区别就是本章的代码求的是方案数，而不是所有方案。调用Backtrack之后不需要关心后面的情况，最终当爬到第 n 阶时，方案数量就会变化。而如果需要求具体的方案，比如将choice放入到方案中，Backtrack递归完成后，当前的choice已经在方案的列表中，这个时候需要把他拿出来，下轮循环再放入其他choice。

[krahets]

Hi，因为在爬楼梯问题中，状态 state 的类型是 int ，我们在调用函数尝试（做出决策、更新状态）时，是将它值传递进去的。每个开启的函数中的 state 都是“独立”的，因此无须回退操作（恢复状态）。

[coder-yangxin]

明白了！

回溯中利用 递归 完成 前进（递） 和 后退（归） 操作，以此往方案中 添加 或 移除 选择项（对应框架代码中的 尝试 和 回退 操作）。

本案例中不记录选择项 并且 上一轮迭代中有自己的的state，所以 后退（归） 时 移除选择项（恢复状态）操作是不必要的

[likz1994]

如果，你的写法是：
state = state + choices；
// 尝试：做出选择，更新状态
backtrack(choices, state, n, res);
// 回退（就需要进行 state的 回退操作）
state = state - choices；

[swaggywilliam]

断断续续学了动态规划一个月了，反复看了三四遍，今天终于感觉通了一些

[CHLK]

大佬牛逼，层层递进，写的很明白，看了这么多解析动态规划的，还是本文最易懂

[macj2010]

这个问题莫名有点像上一章《回溯》里面的《子集》问题，给定一个集合[3,4,5]，求他们和是9的子集有多少种。这个问题换成集合[1,2]，和是n的子集。不同于前面要考虑去重，这里不用考虑。{1，2}、{2，1}被认为是不同的结果。那我很好奇，当然dfs也很不错，但是如果上楼梯的步数变成[1,2,3]，是不是就变成dfs(i)=dfs(i-1)+dfs(i-2)+dfs(i-3)。

[hpstory]

Hi @macj2010 , 是的会变成dfs(i)=dfs(i-1)+dfs(i-2)+dfs(i-3)，动态规划和记忆化搜索是可以相互转换的，回溯的话包含很多重复计算。

[MuZiYuHui]

牛啊，循循渐进，先从回溯法切入问题，再一步一步优化，对我这个初学者来说很好理解

[Vstornzw]

C++
是否可以增加isDirty,写成：

/* 回溯 */
void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
    // 当爬到第 n 阶时，方案数量加 1
    bool isDirty = false;
    if (state == n) {
        res[0]++;
        isDirty = true;
    }
    // 遍历所有选择
    if (!isDirty) {
        for (auto &choice : choices) {
            // 剪枝：不允许越过第 n 阶
            if (state + choice > n)
                continue;
            // 尝试：做出选择，更新状态
            backtrack(choices, state + choice, n, res);
            // 回退
        }
    }
}

[krahets]

这样做不太有必要，直接在记录解后 return 就可以了

[NormanCarrie]

妙啊！！，真的是太妙了，大哥哥，我是小学生，tql

[krahets]

哈哈，你真的是小学生吗？

[haerker]

k神，看到这里突然对动态规划和分治有些模糊，都是将大问题拆分为小问题。我的理解：分治拆分的小问题是独立的，不重复的，未知的，所以需要有“合并”的操作，所以需要递归。而动态规划的小问题具有重复性，已知的，所以可以采用迭代。这样理解正确吗？

[baimizhouu]

正确的。动态规划的特征是Overlapping Subproblems和Optimal Substructure。

[ovo-Tim]

好像还没人发现，14.1.4 Rust 代码可以用解构省去 tmp 变量: (a, b) = (b, a+b);

/* 爬楼梯：空间优化后的动态规划 */
fn climbing_stairs_dp_comp(n: usize) -> i32 {
    if n == 1 || n == 2 {
        return n as i32;
    }
    let (mut a, mut b) = (1, 2);
    for _ in 3..=n {
        (a, b) = (b, a+b);
    }
    b
}