江苏龙网

  1. 首页 > 人文 > >

算法萌新如何学好动态规划（3）( 七 )


因此问题转变为从 N 个数中选取若干个数 ， 使其总和为
算法萌新如何学好动态规划（3）文章插图
， 问有多少种选数方案 。
由于每个数只能选一次 ， 因此我们可以较为容易地将该问题转化为「0/1 背包」模型 。 仿照「0/1 背包」 ， 定义
算法萌新如何学好动态规划（3）文章插图
表示仅考虑前 i 个数 ， 有多少种选数方案使其数字和为 j 。
因此我们可以得到如下「DP 转移方程」：
算法萌新如何学好动态规划（3）文章插图
定义一下初始条件 ，
算法萌新如何学好动态规划（3）文章插图
。 接下来直接套用「0/1 背包」滚动数组版本的代码即可 ， 具体细节见下述代码 。
C++ 代码实现class Solution {public:vector f;int findTargetSumWays(vectorfor(int item:nums) sum += item;if(S < -sum || S > sum || (sum + S) % 2) return 0;a = (S + sum) / 2;f.resize(a + 1);// DP 过程f[0] = 1;for(int i = 0; i < nums.size(); i++)for(int j = a; j >= nums[i]; j--)f[j] += f[j-nums[i]];return f[a];}};322. 零钱兑换?题目描述给定不同面额的硬币 coins 和一个总金额 amount 。 编写一个函数来计算可以凑成总金额所需的最少的硬币个数 。 如果没有任何一种硬币组合能组成总金额 ， 返回 - 1 。
示例 1输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1示例 2输入: coins = [2], amount = 3输出: -1?提示

  • 你可以认为每种硬币的数量是无限的 。
解题思路从 N 类硬币中选取若干个 ， 使得选取硬币的总金额为 M ， 求最少所需的硬币个数 。 很明显这是一道「背包类」问题 ， 且由于每一类硬币可以选取无限个 ， 因此这是一道「完全背包」问题 。
仿照「完全背包」的思路 ， 定义
算法萌新如何学好动态规划（3）文章插图
表示仅考虑前 i 类硬币 ， 其总金额为 j 时最少所需硬币个数 。
因此我们可以得到如下「DP 转移方程」：
算法萌新如何学好动态规划（3）文章插图
定义一下初始条件 ，
算法萌新如何学好动态规划（3）文章插图
。 接下来直接套用「完全背包」滚动数组版本的代码即可 ， 具体细节见下述代码 。
C++ 代码实现class Solution {public:vector f;const int inf = 1e8;int coinChange(vectorf[0] = 0;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++)f[j] = min(f[j], f[j-coins[i]] + 1);if(f[amount] == inf) return -1;else return f[amount];}};?518. 零钱兑换 II题目描述给定不同面额的硬币和一个总金额 。 写出函数来计算可以凑成总金额的硬币组合数 。 假设每一种面额的硬币有无限个 。
示例 1输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+1?5=2+1+1+15=1+1+1+1+1示例 2输入: amount = 3, coins = [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3 。 ?示例 3输入: amount = 10, coins = [10] 输出: 1?提示
算法萌新如何学好动态规划（3）文章插图


推荐阅读


上一篇：新人必看，一个接触币圈2年的人花钱买来的教训

下一篇：MIUI 12.5开启内测报名：首批支持21款机型！今晚发布后开始推送