动态规划—C语言

解题思路:

注意事项:

参考代码:

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#define MAX 200
#define MAX_I 3334 //位数
#define MAX_J 512 //当前最高位的数
int dp[MAX_I][MAX_J] = { 0 };
//dp[i][j]==>>在i位数下，最高位为j的情况下，满足条件的数有多少个
//不考虑位数为0和1


//进位
void restruct_count(int count[MAX])
{
	for(int j = MAX - 1; j >= 0; j--)
	{
		if (count[j] > 10)
		{
			count[j - 1] += count[j] / 10;
			count[j] = count[j] % 10;
		}
		else
		{
			break;
		}
	}
}
int main()
{
	int k = 0, w = 0;
	scanf("%d%d", &k, &w);
	int count[MAX] = { 0 };//满足条件的数
	int n = w / k;//位数
	int mod = w % k;
	if (mod)
	{
		n++;
	}
	//对两位数进行初识化
	//也可以从1位数开始初识化，即dp[1][j]=1;
	for (int j = 1; j < (int)pow(2, k); j++)
	{
		dp[2][j] =(int)pow(2, k) - 1 - j;
	}
	//位数递增
	for (int i = 3; i <= n; i++)
	{
		for (int j = 1; j <= (int)pow(2, k) - i; j++)
		{
			//dp[i][j]=dp[i-1][j+1]+dp[i-1][j+2]+...+dp[i-1][max-i+1]
			//max-i+1==>>在i-1位数下，最高位的最大取值
			for (int x = j + 1; x <=(int)pow(2, k) - i + 1; x++)
			{
				dp[i][j] += dp[i - 1][x];
			}
		}
	}
	w = w - k;//从二位数开始
	for (int i = 2; i <= n; i++)
	{
		   int max = 0;
			if (w < k)
			{
				max = (int)pow(2, w);
				for (int j = 1; j < max; j++)
				{
					count[MAX - 1] += dp[i][j];
				}
				restruct_count(count);
			}
			else
			{
				max = (int)pow(2, k);
				for (int j = 1; j < max; j++)
				{
					count[MAX - 1] += dp[i][j];
				}
				restruct_count(count);
			}
			w = w - k;//进入下一位
	}
	//去0
	int i = 0;
	while (!count[i])
	{
		i++;
	}
	for (i; i < MAX; i++)
	{
		printf("%d", count[i]);
	}
	return 0;
}