连 01 背包都看不懂, 零钱兑换都不会，还能继续走 Coding 这条路吗
資深大佬 : guixiexiezou 4
辞职许久了，思考了很久，觉得自己是不是不太适合当程序员了？最近看算法，刷 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; } 大佬有話說 (74)