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

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

不能