看正月点灯笼老师的笔记 ——动态规划2.2

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int a[100];
int subset[100][100];
int rec_subset(int i,int  s)   // 递归
{
	if (s == 0)
		return 1;
	else if (i == 0)
		return a[0] == s;
	else if (a[i] > s)
		return rec_subset(i - 1, s);
	else
	{
		int A = rec_subset(i - 1, s - a[i]);
		int B = rec_subset(i - 1, s);
		return A || B;
	}
}
int dp_subset(int lon, int S)   // 动态规划
{
	for (int i = 0; i < lon; i++) // 递归出口
	{
		subset[i][0] = 1;
	}
	for (int i = 0; i <= S; i++)  // 递归出口
	{
		subset[0][i] = 0;
	}subset[0][a[0]] = 1;      
	
	for (int i = 1; i < lon; i++)
	{
		for (int j = 1; j <= S; j++)
		{
			if (a[i] > j)    // 递归出口
				subset[i][j] = subset[i - 1][j];
			else
			{
				int A = subset[i - 1][j - a[i]];
				int B = subset[i - 1][j];
				subset[i][j] = A || B;
			}
		}
	}
	return  subset[lon - 1][S];
}
int main(void)
{
	int lon, S;
	while (scanf("%d%d", &lon, &S) != EOF)
	{
		for (int i = 0; i < lon; i++)
		{
			scanf("%d", &a[i]);
		}
		printf("%d\n", rec_subset(lon - 1, S));
		printf("%d\n", dp_subset(lon, S));
	}
	
	system("pause");
	return 0;
}
/*测试数据
6 9
3 34 4 12 5 2
6 13
3 34 4 12 5 2
*/