连 01 背包都看不懂, 零钱兑换都不会，还能继续走 Coding 这条路吗
guixiexiezou · 2020-11-16 12:10:29 +08:00 · 8866 次点击这是一个创建于 1486 天前的主题，其中的信息可能已经有所发展或是发生改变。
辞职许久了，思考了很久，觉得自己是不是不太适合当程序员了？最近看算法，刷 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;
}
 |
1
hubahuba 2020-11-16 12:17:02 +08:00  1
cao
|
 |
2
guixiexiezou OP 而且代码还是错误的.........哎😔
|
 |
3
v2webdev 2020-11-16 12:26:48 +08:00 1
矫情的话，去一亩三分地上吧，V 站不适合。
|
 |
4
crclz 2020-11-16 12:29:14 +08:00 1
0-1 背包，不要试着去理解它，去感受它。
多做几个变形题（做不出来看题解也行），自然就理解了。 |
 |
5
darklowly 2020-11-16 12:30:46 +08:00 13
写程序有两大条路
1 系统类 2 算法类 系统类，不需要那么多的算法，简单的数据，链表，树，hash 就够了。其他的就是计算机系统方面的知识。例如，组成原理，操作系统，设计模式，架构模式。这条路适合智力正常范围的人，因为智力正常的人，更容易感受到困难，就更容易设计简单的系统，反而对设计有好处。 算法类，侧重点就是数学，适合智力好一点的人，反而这类人不容易感受到困难，设计的系统会违反常人的直觉，反而是不好的设计。当然也有很多智商不够，自以为很够的人，既设计不好算法，又搞的很复杂。 所以不要灰心。 |
 |
6
BBCCBB 2020-11-16 12:35:07 +08:00 1
你要有点基础后就好了, 别气馁.. 刚开始时都是这样, 不停的刷, 总结, 系统的学.
0-1 背包可以看看这个 https://www.cnblogs.com/labuladong/p/12455089.html |
|
7
guixiexiezou OP @v2webdev 可能是太久没工作了吧，心又静不下来。多谢指点
|
|
8
guixiexiezou OP @darklowly 嗯嗯，多谢指点。我也觉得我如果继续 coding 下去，最多最多还是只能走工程这条路，也就是所谓的用别别人的轮子
|
|
9
guixiexiezou OP @BBCCBB 多谢，我去看看
|
|
10
guixiexiezou OP @crclz 我再感受 2 天吧，说不定真就领悟了
|
 |
11
rodrick 2020-11-16 12:59:14 +08:00
不要灰心，换个角度想想，你如果转行了又怎么知道自己更适合另外一行呢
|
 |
12
deepall 2020-11-16 13:19:40 +08:00 7
这不是凡尔赛人？
|
 |
14
a62527776a 2020-11-16 13:30:04 +08:00
太牛了（吹捧一波
|
 |
15
keymao 2020-11-16 13:32:38 +08:00
这不就是凡尔赛人
|
 |
16
guchengyehai1 2020-11-16 13:38:02 +08:00 via Android
回溯再加个记忆就和 dp 差不多了
|
 |
17
Mac 2020-11-16 13:38:45 +08:00 via Android 1
我只会百度谷歌，其它的一概不会
|
 |
18
shubo83 2020-11-16 13:42:45 +08:00
可以先当不会算法的野生程序员，比如我
|
 |
19
leido 2020-11-16 13:45:33 +08:00
|
 |
20
wph95 2020-11-16 13:47:40 +08:00 1
|
 |
21
gitgabige 2020-11-16 13:48:22 +08:00
讲道理，我最近也在看（复习）这个。也就看了下简单的 0-1 背包，后面更复杂的就不想看了。我觉得吧，主要是面试公司需要这些，真正工作中用到的凤毛麟角。所谓面试造火箭，工作拧螺丝。
|
|
22
wph95 2020-11-16 13:51:08 +08:00
动归这问题不要慌，这东西是反正常人思路的。不像回溯符合正常人的思维。
得靠多做题才能逐渐掌握的 (大神除外） 背包 dp 记忆化搜索 区间 DP 稍微能知道是个啥就足够了 |
 |
23
cccp2020 2020-11-16 13:54:11 +08:00
动态规划是高阶的算法题了，先学简单的，慢慢再看动态规划，开局就打 boss 绝对是被虐
|
 |
24
gadsavesme 2020-11-16 14:01:30 +08:00
不至于啊，不就是多看多练么，我好多题目都是当时花了半天全部参透，写完提交美滋滋，然后过了几个月回来依旧不大记得。但是有的题反复写的多了，基本就忘不掉了。别怀疑自己毕竟都是普通人，那种看过就会，刷一篇就精通的大佬实在是比不来。
|
 |
25
axex 2020-11-16 14:09:40 +08:00
刷了过几个月忘了
|
 |
26
Gwzlchn 2020-11-16 14:11:41 +08:00 4
楼主您好~我是来鼓励你的 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 背包物品问题真的每步都不是那么显然成立的，所以觉得难是正常的。如果你觉得简单，而并没有仔细思考这些问题只能说明你是背会的答案，而不是理解会的，那又有什么意义呢？ 总而言之：觉得难是好事，这会促进我们思考算法中每个不那么显然的地方。 |
 |
27
dk7952638 2020-11-16 14:46:31 +08:00
如果谷歌和栈溢出不能解决问题，那就去 github 里问候作者
|
|
28
dk7952638 2020-11-16 14:47:38 +08:00 1
其实绝大多数 IT 从业者从事的并不是软件开发，而是代码焊接工
|
 |
29
QingchuanZhang 2020-11-16 15:08:47 +08:00
我一开始也不会，别担心，可能只是教程不合适
|
 |
30
westtide 2020-11-16 15:16:09 +08:00
可以看 mooc 上的算法课？这些问题在算法课上一般都有讲，还有形式化证明。考研的时候看了北大屈婉玲老师的《算法设计与分析》，讲的很透彻和深刻。
|
 |
31
luckcul 2020-11-16 15:27:03 +08:00
多看 多想 多写
孰能生巧 |
 |
32
SWALLOWW 2020-11-16 16:49:19 +08:00
我司软件和算法是分开的，各司其职，不难为程序员搞数学
|
 |
33
Martox 2020-11-16 16:54:51 +08:00
我都快要忘记我应该刷算法这件事情了
|
 |
34
zzzain46 2020-11-16 19:06:49 +08:00
哈哈哈当年学 运筹学 的时候也觉得动态规划和背包问题是有点难的，多学几遍就好，先手动模拟原理和方法，再写代码会好很多
|
 |
35
wowodavid 2020-11-16 20:04:03 +08:00
你要搞明白那些人是“会”了，还是“学会”了，又不是自己想明白的，不就是比你早两天看书看会了吗，有啥好优越的，闻道有先后而已。
|
 |
36
impl 2020-11-16 21:50:56 +08:00 via iPad
多刷题，不懂的话背下来，找张纸默写几遍，总会有理解的时候
|
 |
37
lithbitren 2020-11-16 22:08:53 +08:00
动态规划题型太多，背包只是基础，遇到没见过的 DP 题型，除了顶尖大神，剩下基本不可能在面试的时候做出来，所以面试的时候一般就算考动归也是基础动归，多刷刷题就好了
|
 |
39
raaaaaar 2020-11-16 22:37:19 +08:00 via Android
垃圾算法，毁我青春
|
 |
40
RedBeanIce 2020-11-16 22:40:52 +08:00 1
凡尔赛。
|
|
41
QingchuanZhang 2020-11-16 23:01:38 +08:00
|
 |
42
yekern 2020-11-17 07:31:49 +08:00 1
刷波数据结构以后在去刷 leetcode
|
 |
43
b00tyhunt3r 2020-11-17 08:47:11 +08:00
马一个
|
 |
44
dingyaguang117 2020-11-17 09:20:58 +08:00 via iPhone
题目做多了就有感觉了 和数学一样
|
|
45
guixiexiezou OP 认真看了下每个回复，感谢鼓励。昨晚研究了一晚上，终于把基础的 01 背包看懂了，但在二维数组变换成一维数组又看不懂了。关于算法这个，工作中用的概率确实太低太低了（可能和我职业层次位置相对低下有关，之前做游戏服务端，无论是路径计算，技能伤害计算还是常规业务处理，上面的算法我一个都用不到）
|
 |
46
user8341 2020-11-17 10:06:58 +08:00
@guixiexiezou 路径计算是不是也要用到算法啊？
|
 |
47
lewis89 2020-11-17 10:45:37 +08:00
@guixiexiezou #45 本来这些算法的意义就不大，至少在 N 很小的时候就没什么卵用，有这个功夫去实现这样花俏的算法，还不如直接全部暴力枚举，你搞一堆剪枝 递推 打表 结果发现 N 很小，维护这个代码的成本远比优化带来的收益高得多，而恰恰大部分场景 N 都很小，所以实际场景 DP 没什么人去用，极少我觉得暴力枚举比 DP 可靠，而且实现容易 测试简单。
|
|
48
lewis89 2020-11-17 10:46:50 +08:00
@user8341 #46 路径有专门的最短路径算法 还有 R* 这些都是现成的套路算法，只要把游戏里面的地图 弄好成邻接矩阵就行了
|
 |
50
gongshishao126 2020-11-17 10:48:52 +08:00
@rodrick 杀人诛心呐~
|
|
51
lewis89 2020-11-17 10:55:52 +08:00
@Gwzlchn #26 关键是 N 很小的时候，费这么大的劲去搞递推公式的意义真的不大，大部分时候 N 都很小，没必要去实现这样花俏 难以维护的算法，与其这样 为啥不直接暴力枚举？
|
 |
53
Chenamy2017 2020-11-17 11:01:28 +08:00
话说作为十年老程序员的我，还没看过 01 背包问题，你钻牛角尖了，程序员有很多方面的，不要揪着算法深入，算法无穷尽，基本的掌握了就可以做业务了。有几个程序员是算法大牛的，市场也不需要那么多的算法大牛。
|
 |
54
justest123 2020-11-17 11:01:55 +08:00
是我对凡尔赛的理解有偏差么？为什么这种吐槽+半诉苦的帖子都会有人刷凡尔赛？有病吧
数学思维或者说逻辑思维不是非常好，这类算法题一样也是感觉头大，倒是没怀疑自己没救了，大概还是看开点，什么能力做什么事，难为自己干嘛呢 |
 |
55
Phariel 2020-11-17 11:05:58 +08:00 via iPhone
自信点 我有些 easy 也做不到最优解 你太魔怔了🐶
|
 |
56
Felldeadbird 2020-11-17 11:14:12 +08:00
CURD 也是一件快活牛逼的事情。写软件又不是时刻用到算法。
|
 |
57
vevlins 2020-11-17 11:24:55 +08:00 1
不会算法的程序员多的是。
程序员的三个方向：性能的极致优化、业务的极致理解、系统的极致设计。做到一个就可以了。 |
 |
58
coderunI 2020-11-17 11:31:22 +08:00
看不起，代码焊接工吗？
|
 |
59
learningman 2020-11-17 11:33:05 +08:00
看不起，手上没几块 ICPC World Final Gold 配写代码？ NOI 国集估计也就勉强写写 CURD 吧
|
 |
60
cumshot 2020-11-17 11:42:53 +08:00
不能
|
 |
61
tianhualefei 2020-11-17 13:49:40 +08:00 via Android
背包问题在力扣（ leetcode ）属于中等难度。你这既没有正确认识问题的难度，也没正确认识自己的水平。
|
 |
62
totoro52 2020-11-17 13:54:48 +08:00
这里也有凡尔赛人？
|
|
63
guixiexiezou OP @tianhualefei 我看了下，确实是属于中等难度。也就是说这就是我思维的极限了。
|
 |
64
ochatokori 2020-11-17 14:07:37 +08:00 via Android
我只会快排，我应该转行吗
|
|
65
guixiexiezou OP @totoro52 当你所有视频面(中大厂级别)都挂了的时候，也许你就不会这么认为了，反而会从另外一个角度思考问题，无论是牛角尖也好，还是感悟人生也好
|
|
66
guixiexiezou OP @user8341 寻路一般都用改进版 A 星算法，一般都用现成的库例如 LIBGDX 等，也会用上一代人遗留的代码，直接调用接口。需要自己完整实现的场景不多
|
 |
67
jay4497 2020-11-17 14:52:25 +08:00
哪条路上都有各种级别的人，大神都那么多了，咱就不去凑那个热闹了，安心做个菜鸡。。。
说不适合这条路那不至于不至于。。。 |
 |
68
billma 2020-11-17 16:45:17 +08:00
你这让只会 vb 的我情何以堪...
|
 |
69
calabash519 2020-11-17 16:53:17 +08:00
建议转行
|
 |
71
1039460820 2020-11-17 18:14:12 +08:00
小白前来为楼主加油，随便看看大佬们的推荐，V2ex 万岁！
|
 |
72
CoderGeek 2020-11-17 18:21:40 +08:00
用过就忘 老被说 公司里经常被人怼 不是会个啥算法就怎么样，然后离职换下家又得温习一遍 哈哈哈
|
 |
73
hejw19970413 2020-11-17 18:28:18 +08:00
先会学会抄，后会学，然后是理解，这是一个痛苦的过程
|
|
74
darklowly 2020-11-17 22:00:58 +08:00
@leido 和算法高不高级么关系的，重要是两条不同的方向。不信的话，你可以调研一下绝大部分工程师，工作中用过动态规划吗？
绝大部份工程师职业瓶颈根本就不在算法上面，是在设计上面，能够用简单优美的方法解决问题，比算法更重要。 我观察过很多工程师，智力正常，投资很多时间去搞算法，结果是，算法也搞不好，代码也写不好，这种情况在国内非常普遍。甚至很多工程师工作 10 年以上，分解一个函数都分解不好。 go 语言有一个开源的 web 框架：beego，在国内受到了大量的追捧，里面的代码写得非常差，设计也非常潦草。如果你仔细去思考这个问题，会非常有意思： 1 为什么一个喜欢技术的程序员写出了非常差的代码，还好意思公开发表？并且还出书教人？ 2 为什么大量的用户会去追捧这样一个很差的框架？这些用户里面大量是小白，没有鉴别能力，可以理解，为什么很多很有经验的工程师也没有鉴别能力？如果连基本的鉴别能力都不具备，设计能力就更不具备了。 他们缺乏的是算法能力吗？还是基本的设计能力和鉴别能力？ 这些设计和鉴别能力，应该怎么才能学到呢？无非就是去多学习经典的设计方法。而这些设计方法大多在第一条路上面学习。 PS：基本的数据结构和算法是需要的。 |
 |
75
gy0624ww 2020-11-20 14:26:28 +08:00
特么的，今天我才知道凡尔赛人是啥意思，我以为你们讨论的是一道 leetcode 题目叫凡尔赛人呢
|
Select Language