蓝桥杯算法提高VIP-摆花 （C++代码）

解题思路:

记忆化搜索即可，MOD的位置有讲究？是的

记忆化对于复杂度简直就是降维打击。。。

这个题可以写成带回溯的也可以写成不带回溯的，就是记录每种花剩余的数量，尽量写成不带回溯的比较好

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <stdio.h>

#define MOD 1000007
#define N 110
using namespace std;

int a[N];
int n, m;

long long cache[N][N];

long long solve_dfs(int index, int res)
{
	if (cache[index][res])
		return cache[index][res];
	
	if (res == 0) return 1;
	else if (index >= n) return 0;
	else
	{
		long long ans = 0;
		for (long long i = 0; i <= a[index]; i++)
			if (res - i >= 0)
				ans += solve_dfs(index + 1, res - i);
		ans %= MOD;
		cache[index][res] = ans;
		return ans;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << solve_dfs(0, m) << endl;
	return 0;
}

//朴素dp解法

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <stdio.h>

#define MOD 1000007
#define N 110
using namespace std;

int a[N];
int n, m;
long long dp[N][N];

long long solve_dp()
{
	for (int i = 0; i <= n; i++)
		dp[i][0] = 1;

	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 1; j <= m; j++)
		{
			long long ans = 0;
			for (long long k = 0; k <= a[i]; k++)
				if (j - k >= 0)
					ans += dp[i + 1][j - k];
			ans %= MOD;
			dp[i][j] = ans;
		}
	}

	return dp[0][m];
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cout << solve_dp() << endl;
	return 0;
}