组成aim的方法数2（无限多张）

本文主要是介绍组成aim的方法数2（无限多张），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：arr是面值数组，其中的值都是正数且没有重复，再给定一个正数aim，每个值都认为是一种面值，且认为张数是无线的，返回组成aim的方法数。例如，arr=[1,2]，aim=4，方法有，1+1+1+1，1+1+2，2+2，一共3种方法，所以返回3。

way：//arr[index...]所有的面值,每一个面值都可以选择无限多张，组成rest元的方法数。for(int zhang=0; rest-zhang*arr[index]>=0; zhang++)

#include<iostream>
#include<vector>
using namespace std;//arr[index...]所有的面值,每一个面值都可以选择无限多张，组成rest元的方法数。
int process(vector<int>arr, int index, int rest)
{if(index==arr.size()) {return rest==0?1:0;}int way=0;for(int zhang=0; rest-zhang*arr[index]>=0; zhang++){way+=process(arr, index+1, rest-zhang*arr[index]);}return way;
}int coinWay(vector<int>arr, int aim)
{return process(arr, 0, aim);
}

way2：dp版

int dpWay(vector<int>arr, int aim)
{int N=arr.size();vector<vector<int>>dp(N+1, vector<int>(aim+1));dp[N][0]=1;for(int index=N-1; index>=0; index--){for(int rest=0; rest<=aim; rest++){int way=0;for(int zhang=0; zhang*arr[index]<=rest; zhang++){way+=dp[index+1][rest-zhang*arr[index]];}dp[index][rest]=way;}}return dp[0][aim];
}

这篇关于组成aim的方法数2（无限多张）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---