连 01 背包都看不懂, 零钱兑换都不会，还能继续走 Coding 这条路吗

[guixiexiezou]

辞职许久了，思考了很久，觉得自己是不是不太适合当程序员了？最近看算法，刷 leetcode，简单的基本都会（相信在做的各位也没几个不会的），遇到最优解的，动态规划的，基本一个都不会了（哭。。。）

然后昨天今天特意看了下 01 背包问题，我发现我居然看不懂了。。。

今天看到一个简单的零钱兑换问题。只会用回溯法。。。我是不是没救了。。。

附代码

private int change0(int[] arr, int target) {
        Arrays.sort(arr);
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int index = arr.length-1;
        while (!stack.isEmpty() || index >= 0) {
            if (index < 0) {
                if (stack.isEmpty()) return -1; //找不到
                int last = stack.pop();
                target += arr[last];
                index = last-1;
                continue;
            }
            if (arr[index] == target) {
                return stack.size()+1;
            } else if (arr[index] > target) {
                index--;
            } else {
                target -= arr[index];
                stack.push(index);
            }
        }
        return -1;
}

[hubahuba]

cao

[guixiexiezou]

而且代码还是错误的.........哎😔

[v2webdev]

矫情的话，去一亩三分地上吧，V 站不适合。

[crclz]

0-1 背包，不要试着去理解它，去感受它。

多做几个变形题（做不出来看题解也行），自然就理解了。

[darklowly]

写程序有两大条路

1 系统类
2 算法类

系统类，不需要那么多的算法，简单的数据，链表，树，hash 就够了。其他的就是计算机系统方面的知识。例如，组成原理，操作系统，设计模式，架构模式。这条路适合智力正常范围的人，因为智力正常的人，更容易感受到困难，就更容易设计简单的系统，反而对设计有好处。

算法类，侧重点就是数学，适合智力好一点的人，反而这类人不容易感受到困难，设计的系统会违反常人的直觉，反而是不好的设计。当然也有很多智商不够，自以为很够的人，既设计不好算法，又搞的很复杂。

所以不要灰心。

[BBCCBB]

你要有点基础后就好了, 别气馁.. 刚开始时都是这样, 不停的刷, 总结, 系统的学.

0-1 背包可以看看这个 https://www.cnblogs.com/labuladong/p/12455089.html

[guixiexiezou]

@v2webdev 可能是太久没工作了吧，心又静不下来。多谢指点

[guixiexiezou]

@darklowly 嗯嗯，多谢指点。我也觉得我如果继续 coding 下去，最多最多还是只能走工程这条路，也就是所谓的用别别人的轮子

[guixiexiezou]

@BBCCBB 多谢，我去看看

[guixiexiezou]

@crclz 我再感受 2 天吧，说不定真就领悟了

[rodrick]

不要灰心，换个角度想想，你如果转行了又怎么知道自己更适合另外一行呢

[deepall]

这不是凡尔赛人？

[tgich]

@deepall 这不就是凡尔赛人

[a62527776a]

太牛了（吹捧一波

[keymao]

这不就是凡尔赛人

[guchengyehai1]

回溯再加个记忆就和 dp 差不多了

[Mac]

我只会百度谷歌，其它的一概不会

[shubo83]

可以先当不会算法的野生程序员，比如我

[leido]

楼主, 背包九讲看了吗?

DP 根本算不上什么高级算法, 扯不到什么系统和算法上去 @darklowly

背包问题我高中就会解了(自学), 现在还在做运维 , 我是不是比楼主更菜

[wph95]

背包问题一个教程就可以搞定 :)
https://github.com/tianyicui/pack
// 背包九讲永远滴神

[gitgabige]

讲道理，我最近也在看（复习）这个。也就看了下简单的 0-1 背包，后面更复杂的就不想看了。我觉得吧，主要是面试公司需要这些，真正工作中用到的凤毛麟角。所谓面试造火箭，工作拧螺丝。

[wph95]

动归这问题不要慌，这东西是反正常人思路的。不像回溯符合正常人的思维。
得靠多做题才能逐渐掌握的 (大神除外）
背包 dp 记忆化搜索 区间 DP 稍微能知道是个啥就足够了

[cccp2020]

动态规划是高阶的算法题了，先学简单的，慢慢再看动态规划，开局就打 boss 绝对是被虐

[gadsavesme]

不至于啊，不就是多看多练么，我好多题目都是当时花了半天全部参透，写完提交美滋滋，然后过了几个月回来依旧不大记得。但是有的题反复写的多了，基本就忘不掉了。别怀疑自己毕竟都是普通人，那种看过就会，刷一篇就精通的大佬实在是比不来。

[axex]

刷了过几个月忘了

[Gwzlchn]

楼主您好~我是来鼓励你的 hhh

我这学期刚选了我们学校的算法课（卜东波教授），实际上，老师上课也会说，DP 、贪心算法的每个细微的策略并不是那么显然的，我们不可能对每道题都背诵算法的策略，重要的是我们应该如何从问题的特点构造出来一种合适的策略。

举个例子，我看楼上有说“九讲背包”这个文档不错，那么我对下面这句话问几个问题希望楼主思考一下：为什么我们要在状态方程中使用“前 i 个物品”这种定义状态转移的策略？如果用“前 i 个”这种表述，那么我们对物品集合进行排序了吗（注意，集合是无序的，所以你不能对一个集合说“前 i 个”）？如果是排序的，那么我们应该用什么样的定序方法？

或者考虑这种更新子问题的策略：我们每步都考虑物品集合中的每个物品是否能放入背包中，然后下一步进行同样的策略呢？这种方法可不可行呢？

“用子问题定义状态：即 F[i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}
”

你看，这个 01 背包物品问题真的每步都不是那么显然成立的，所以觉得难是正常的。如果你觉得简单，而并没有仔细思考这些问题只能说明你是背会的答案，而不是理解会的，那又有什么意义呢？

总而言之：觉得难是好事，这会促进我们思考算法中每个不那么显然的地方。

[dk7952638]

如果谷歌和栈溢出不能解决问题，那就去 github 里问候作者

[dk7952638]

其实绝大多数 IT 从业者从事的并不是软件开发，而是代码焊接工

[QingchuanZhang]

我一开始也不会，别担心，可能只是教程不合适

[westtide]

可以看 mooc 上的算法课？这些问题在算法课上一般都有讲，还有形式化证明。考研的时候看了北大屈婉玲老师的《算法设计与分析》，讲的很透彻和深刻。

[luckcul]

多看 多想 多写
孰能生巧

[SWALLOWW]

我司软件和算法是分开的，各司其职，不难为程序员搞数学

[Martox]

我都快要忘记我应该刷算法这件事情了

[zzzain46]

哈哈哈当年学 运筹学 的时候也觉得动态规划和背包问题是有点难的，多学几遍就好，先手动模拟原理和方法，再写代码会好很多

[wowodavid]

你要搞明白那些人是“会”了，还是“学会”了，又不是自己想明白的，不就是比你早两天看书看会了吗，有啥好优越的，闻道有先后而已。

[impl]

多刷题，不懂的话背下来，找张纸默写几遍，总会有理解的时候

[lithbitren]

动态规划题型太多，背包只是基础，遇到没见过的 DP 题型，除了顶尖大神，剩下基本不可能在面试的时候做出来，所以面试的时候一般就算考动归也是基础动归，多刷刷题就好了

[asanelder]

@darklowly #5 前者+1

[raaaaaar]

垃圾算法，毁我青春

[RedBeanIce]

凡尔赛。

[QingchuanZhang]

https://github.com/SamZhangQingChuan/Editorials/tree/master/%E9%A2%98%E8%A7%A3/%E6%AF%94%E8%B5%9B/Atcoder%20Educational%20DP%20Contest%20Editorial 动态规划搞不明白不妨试试这个

[yekern]

刷波数据结构以后在去刷 leetcode

[b00tyhunt3r]

马一个

[dingyaguang117]

题目做多了就有感觉了 和数学一样

[guixiexiezou]

认真看了下每个回复，感谢鼓励。昨晚研究了一晚上，终于把基础的 01 背包看懂了，但在二维数组变换成一维数组又看不懂了。关于算法这个，工作中用的概率确实太低太低了（可能和我职业层次位置相对低下有关，之前做游戏服务端，无论是路径计算，技能伤害计算还是常规业务处理，上面的算法我一个都用不到）

[user8341]

@guixiexiezou 路径计算是不是也要用到算法啊？

[lewis89]

@guixiexiezou #45 本来这些算法的意义就不大，至少在 N 很小的时候就没什么卵用，有这个功夫去实现这样花俏的算法，还不如直接全部暴力枚举，你搞一堆剪枝 递推 打表 结果发现 N 很小，维护这个代码的成本远比优化带来的收益高得多，而恰恰大部分场景 N 都很小，所以实际场景 DP 没什么人去用，极少我觉得暴力枚举比 DP 可靠，而且实现容易 测试简单。

[lewis89]

@user8341 #46 路径有专门的最短路径算法 还有 R* 这些都是现成的套路算法，只要把游戏里面的地图 弄好成邻接矩阵就行了

[lewis89]

@user8341 #46 搞错了应该是 A*算法，最近玩 R 星的游戏太多

[gongshishao126]

@rodrick 杀人诛心呐~

[lewis89]

@Gwzlchn #26 关键是 N 很小的时候，费这么大的劲去搞递推公式的意义真的不大，大部分时候 N 都很小，没必要去实现这样花俏 难以维护的算法，与其这样 为啥不直接暴力枚举？

[no1xsyzy]

@darklowly 智商够，但自以为不够的人，是不是无敌了？（

[Chenamy2017]

话说作为十年老程序员的我，还没看过 01 背包问题，你钻牛角尖了，程序员有很多方面的，不要揪着算法深入，算法无穷尽，基本的掌握了就可以做业务了。有几个程序员是算法大牛的，市场也不需要那么多的算法大牛。

[justest123]

是我对凡尔赛的理解有偏差么？为什么这种吐槽+半诉苦的帖子都会有人刷凡尔赛？有病吧

数学思维或者说逻辑思维不是非常好，这类算法题一样也是感觉头大，倒是没怀疑自己没救了，大概还是看开点，什么能力做什么事，难为自己干嘛呢

[Phariel]

自信点 我有些 easy 也做不到最优解 你太魔怔了🐶

[Felldeadbird]

CURD 也是一件快活牛逼的事情。写软件又不是时刻用到算法。

[vevlins]

不会算法的程序员多的是。

程序员的三个方向：性能的极致优化、业务的极致理解、系统的极致设计。做到一个就可以了。

[coderunI]

看不起，代码焊接工吗？

[learningman]

看不起，手上没几块 ICPC World Final Gold 配写代码？ NOI 国集估计也就勉强写写 CURD 吧

[cumshot]

不能

[tianhualefei]

背包问题在力扣（ leetcode ）属于中等难度。你这既没有正确认识问题的难度，也没正确认识自己的水平。

[totoro52]

这里也有凡尔赛人？

[guixiexiezou]

@tianhualefei 我看了下，确实是属于中等难度。也就是说这就是我思维的极限了。

[ochatokori]

我只会快排，我应该转行吗

[guixiexiezou]

@totoro52 当你所有视频面(中大厂级别)都挂了的时候，也许你就不会这么认为了，反而会从另外一个角度思考问题，无论是牛角尖也好，还是感悟人生也好

[guixiexiezou]

@user8341 寻路一般都用改进版 A 星算法，一般都用现成的库例如 LIBGDX 等，也会用上一代人遗留的代码，直接调用接口。需要自己完整实现的场景不多

[jay4497]

哪条路上都有各种级别的人，大神都那么多了，咱就不去凑那个热闹了，安心做个菜鸡。。。

说不适合这条路那不至于不至于。。。

[billma]

你这让只会 vb 的我情何以堪...

[calabash519]

建议转行

[weidaizi]

@darklowly 十分认同

[1039460820]

小白前来为楼主加油，随便看看大佬们的推荐，V2ex 万岁！

[CoderGeek]

用过就忘 老被说 公司里经常被人怼 不是会个啥算法就怎么样，然后离职换下家又得温习一遍 哈哈哈

[hejw19970413]

先会学会抄，后会学，然后是理解，这是一个痛苦的过程

[darklowly]

@leido 和算法高不高级么关系的，重要是两条不同的方向。不信的话，你可以调研一下绝大部分工程师，工作中用过动态规划吗？

绝大部份工程师职业瓶颈根本就不在算法上面，是在设计上面，能够用简单优美的方法解决问题，比算法更重要。

我观察过很多工程师，智力正常，投资很多时间去搞算法，结果是，算法也搞不好，代码也写不好，这种情况在国内非常普遍。甚至很多工程师工作 10 年以上，分解一个函数都分解不好。

go 语言有一个开源的 web 框架：beego，在国内受到了大量的追捧，里面的代码写得非常差，设计也非常潦草。如果你仔细去思考这个问题，会非常有意思：

1 为什么一个喜欢技术的程序员写出了非常差的代码，还好意思公开发表？并且还出书教人？

2 为什么大量的用户会去追捧这样一个很差的框架？这些用户里面大量是小白，没有鉴别能力，可以理解，为什么很多很有经验的工程师也没有鉴别能力？如果连基本的鉴别能力都不具备，设计能力就更不具备了。


他们缺乏的是算法能力吗？还是基本的设计能力和鉴别能力？


这些设计和鉴别能力，应该怎么才能学到呢？无非就是去多学习经典的设计方法。而这些设计方法大多在第一条路上面学习。

PS：基本的数据结构和算法是需要的。

[gy0624ww]

特么的，今天我才知道凡尔赛人是啥意思，我以为你们讨论的是一道 leetcode 题目叫凡尔赛人呢