连 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;
}

[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]

凡尔赛。