钱包问题一
我们给定一个数组 arr 数组里面的值表示任意一张面值的钞票
每张钞票代表的值可能相同 但是我们认为它们是不同的钞票
现在我们给定一个 val 值 请问有多少种组合方案可以让val值为0
递归解法
还是一样 我们首先来想函数
它要返回给我们一个组合的最大值 所以说我们的返回值要是一个int类型的数值
我们要遍历整个money数组 所以说我们需要这个数组和一个index参数来遍历
接着我们需要一个rest参数来记录剩余零钱的数目
整体函数如下
int process(vector<int>& money , int index , int rest)
接下来我们开始想base case
这道题目中有两个变化的量 我们首先向有没有可能会因为index而终止递归呢？
当然有 如果index越界了 那么我们的递归也就终止了
有没有可能因为rest而终止递归呢 ？
当然有 如果剩余零钱的数目为0 我们就终止递归了
if (rest < 0) { return 0; } int N = static_cast<int>(money.size()); if (index == N) { return rest == 0 ? 1 : 0; }
接下来开始列举可能性 对于这种从左往右的模型来说 可能性就是要和不要两种情况
所以说我们直接列出这两种可能性之后想加即可
int process(vector<int>& money , int index , int rest) { if (rest < 0) { return 0; } int N = static_cast<int>(money.size()); if (index == N) { return rest == 0 ? 1 : 0; } int p1 = process(money , index + 1 , rest); int p2 = process(money , index +1 , rest - money[index]); return p1 + p2; }
动态规划
我们首先观察递归函数
int process(vector<int>& money , int index , int rest)
我们可以发现 其中变化的变量有 index 和 rest
所以说我们可以围绕着index 和 rest建立一张二维表
index 的大小是 0 ~ index 大小是index + 1
rest 的大小是 0 ~ rest 大小是rest + 1
我们建立完一个二维表之后就可以根据base case填写数据了
根据
if (index == N) { return rest == 0 ? 1 : 0; }
我们可以得出
dp[N][0] = 1;
接着我们来看位置依赖关系
它依赖于下面一行的两个格子
所以说我们从最下面的倒数第二行开始填写数据 为了防止越界问题 我们再写一个pickup函数
完整代码如下
int dpprocess(vector<int>& money , int rest) { int N = static_cast<int>(money.size()); vector<vector<int>> dp(N + 1 , vector<int>(rest + 1 , 0)); dp[N][0] = 1; for (int row = N - 1; row >= 0; row--) { for (int col = 0; col <= rest; col++) { dp[row][col] = pickupdp(row + 1 , col , dp , N , rest) + pickupdp(row + 1 , col - money[row] , dp , N , rest); } } return dp[0][rest]; }
钱包问题二
我们给定一个数组 arr 数组里面的值表示任意一张面值的钞票 arr内部值不同
每一个arr中的元素代表有无数张钞票
现在我们给定一个 val 值 请问有多少种组合方案可以让val值为0
这个问题和问题一的区别就是 在问题2中 我们的钱包有无数张钞票 只是它们的面值不同 要我们求解法
递归版本
我们首先来想 我们要写什么样的一个递归函数
我们要让这个函数返回一个最大的组合方案 所以返回值是一个int类型的数据
而我们要在一个数组中选取数据 所以自然而然的想到使用index遍历
最后我们还需要一个rest来表示剩余值 整体表示如下
int process(vector<int>& money , int index , int rest)
接着就是想base case 这一步照抄钱包问题一即可
到了列举可能性的这一步就有点意思了
此时的问题就从要不要变为了两个问题
- 要不要？
- 要的话要几个
所以说我们的代码也要转变下
int p1 = process(money , index + 1 , rest); // how many ? int p2 = 0; for (int fix = 1 ; fix * money[index] <= rest; fix++) { p2 += process(money , index + 1 , rest - fix * money[index]); }
可能性1就是我们不要这种类型的钞票了
可能性2就是我们要这种类型的钞票 一张张枚举 知道rest小于0为止
当然我们其实可以让fix从0开始 这样就不需要可能性1了
整体代码表示如下
int process(vector<int>& money , int index , int rest) { if (rest < 0) { return 0; } int N = static_cast<int>(money.size()); if (index == N) { return rest == 0 ? 1 : 0; } int p1 = process(money , index + 1 , rest); // how many ? int p2 = 0; for (int fix = 1 ; fix * money[index] <= rest; fix++) { p2 += process(money , index + 1 , rest - fix * money[index]); } return p1 + p2; }
动态规划
我们首先观察递归函数
int process(vector<int>& money , int index , int rest)
我们可以发现 变量只有index 和rest
所以我们可以围绕着index和rest来做一张二维表
index 的大小是 0 ~ index 大小是index + 1
rest 的大小是 0 ~ rest 大小是rest + 1
我们建立完一个二维表之后就可以根据base case填写数据了
根据
if (index == N) { return rest == 0 ? 1 : 0; }
我们可以得出
dp[N][0] = 1;
接下来我们来看为止依赖关系
我们可以发现这个位置依赖于下面一行的数据具体的格子数目不确定
所以说我们就可以写出这样子的代码
for (int row = N - 1; row >= 0; row--) { for(int col = 0; col <= rest; col++) { int ways = 0; for (int fix = 0; fix * money[row] <= rest; fix++) { ways += pickupdp(row + 1 , col - fix * money[row] , dp , N , rest ); } dp[row][col] = ways; } }
动态规划优化
我们还是来观察下图
我们可以发现蓝色格子依赖的红色格子其实只比黑色格子依赖的红色格子少一个
也就是说我们可以这么转化
黑色格子依赖于蓝色格子和它下面的一个红色格子
于是我们的代码就可以这样子改写
int dpprocess(vector<int>& money , int rest) { int N = static_cast<int>(money.size()); vector<vector<int>> dp(N + 1 , vector<int>(rest + 1 , 0)); dp[N][0] = 1; for (int row = N - 1; row >= 0; row--) { for(int col = 0; col <= rest; col++) { dp[row][col] = pickupdp(row , col - money[row] , dp , N ,rest) + pickupdp(row + 1 , col , dp , N , rest); } } return dp[0][rest]; }
这样子我们就把原来的三个for循环优化成为了两个for循环 效率提高了不少
钱包问题三
我们给定一个数组 arr 数组里面的值表示任意一张面值的钞票 arr内部有相同值的钞票 我们认为值相同的钞票位置可以随意替换 （和题目一不同 题目一中每张钞票都是不同的 ）
现在我们给定一个 val 值 请问有多少种组合方案可以让val值为0
这问题其实是题目二的变形
这里我提供一种思路将其转化为题目二 具体的代码大家可以自己尝试下
我们统计有多少种不同的钞票 并且将这些钞票添加到一个数组中
统计每个钞票的数目 再做一个数组
其中 第一个数组的用途和钱包问题二中的用途一样 而第二个数组则约束了每张钞票最多能取多少
之后按照钱包问题二的思路去做即可
