暴力递归和动态规划解决数组累加和等于特定值的问题（C++实现）

接上一篇博客，又重新找了一个动态规划的题，加深对动态规划的理解。

题目：给定一个数组（数组的值都是正数），和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或false

#include<iostream>
#include<vector>
using namespace std;
class Solution
{
public:
	bool isSum(vector<int> v, int i, int sum, int aim)//暴力递归
	{
		if (i == v.size())
			return sum == aim;
		return isSum(v, i + 1, sum + v[i], aim) || isSum(v, i + 1, sum, aim);
	}
	bool isSum2(vector<int> v,int aim)//动态规划
	{
		vector<vector<bool>> dp(v.size()+1, vector<bool>(aim+1, false));
		for (int i = 0; i <= v.size(); ++i)
		{
			dp[i][aim] = true;
		}
		for (int i = v.size() - 1; i >= 0; --i)
		{
			for (int j = aim - 1; j >= 0; --j)
			{
				dp[i][j] = dp[i + 1][j];
				if (j + v[i] <= aim)
				{
					dp[i][j] = dp[i][j] || dp[i + 1][j + v[i]];
				}					
			}
		}			
		return dp[0][0];
	}
};
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(7);
	Solution s;
	cout << s.isSum(v, 0, 0, 9) << endl;
	cout << s.isSum2(v, 9) << endl;
	system("pause");
	return 0;
}

暴力递归：在vector的每一位都可以选择要不要当前位的值，i=0表示在vector的0位置，sum表示在此位置形成的累加和，当i=v.size()时，判断累加和sum是否等于aim，当i<v.size()，就递归。

动态规划：分析可变参数，可变参数是 i 和 i 位置形成的累加和 j，i 的范围为0到vector的size()， j 的范围是0到aim，两个参数，动态规划表就是二维数组，basecase是最后一列的，也就是 j =aim的值为true，最后一行也是basecase，除了(3,aim)位置为true，其他位置的值都是false，我们要求的就是dp[0][0]的值，从下去倒推dp[0][0]的值，看dp[0][0]是否为true，意思就是如果dp[0][0]=true，那么dp[3][aim]就为true，也就是说存在数组的累加和等于aim。

参考：https://blog.****.net/as1072966956/article/details/82993524