解法总结

动态规划背包问题 这道题是一个典型的01背包问题，只是在处理的时候遇到了递增和递减的问题，最开始很不理解的原因是我对dp的二维数组填充过程以及依赖关系没有明确清晰的认知，再加上在对找零钱这道题目中有递增操作的影响下，一直没能顺利写出正确的过程来。长话短说，这里主要涉及到一个本回合要选择的价值内容对上一轮次的占用问题。 请看如下期望的递增模板 1234567891011121314151617vector<int> f(target + 1, INT_MIN);f[0] = 0;int s = 0;for (int x : nums) { for (int j = 1; j <= target; j++) { if (j >= x) { if (f[j - x] != INT_MIN) { f[j] = max(f[j], f[j - x] + 1); // } } cout << f[j]<<" , "; } cout &l ...