C++实现的动态规划求解分解为若干素数之和的方案总数

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式

#include
 
using namespace std;
 
typedef long long ll;
 
const int N = 1010;
 
int n, m;
int primes[N], cnt = 0;
ll f[N];
bool st[N];
 
void is_prime(int n)
{
	for(int i = 2; i <= n; i ++)
	{
		if(!st[i])primes[cnt ++] = i;
		for(int j = 0; primes[j] <= n / i; j ++)
		{
			st[primes[j] * i] = true;
			if(i % primes[j] == 0)break;
		}
	}
}
 
int main()
{	
    cin >> m;
    
    is_prime(m);
    
    f[0] = 1;
    for(int i = 0; i < cnt; i ++)
    {
        for(int j = primes[i]; j <= m; j ++)
        {
            f[j] += f[j - primes[i]];
        }
    }
    
    cout << f[m];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

这是一个使用C++实现的动态规划求解分解为若干素数之和的方案总数的代码，以下是它的解释：

定义常量N为1010。

定义变量n和m，其中m表示待分解的正整数。

定义数组primes[N]，用于存储小于等于n的所有素数。

定义变量cnt，表示素数的个数。

定义数组f[N]，用于存储分解为i的方案总数。

定义数组st[N]，用于判断一个数是否是素数。

函数is_prime(int n)用于计算小于等于n的素数，具体实现方式为埃氏筛法。

主函数中，首先输入待分解的正整数m，然后调用is_prime()函数计算小于等于m的素数。

初始化f[0]=1，表示分解为0的方案只有1种，即不选任何素数。

使用两重for循环遍历每个素数primes[i]，在内层for循环中，枚举从primes[i]到m的所有数j，并计算包含primes[i]的方案总数f[j] += f[j - primes[i]]。

最后输出f[m]的值，即分解为m的方案总数。

总的来说，这段代码的实现方式与前面的C语言代码大致相同，采用了埃氏筛法和动态规划的思路。需要注意的是，在C++中，数组下标从0开始，而在C语言中下标从1开始。此外，在C++中long long类型需用ll代替，而在C语言中需使用long long或者long long int。

primes 数组中储存的是素数。在循环枚举 (2, n] 区间内的数时，如果当前数 i 是素数，则将其存入 primes 数组中；同时，在循环内部，按照与该数相乘得到小于等于 n 的数 j = primes[k] (k < i)，将该数标记为非素数（即 st[j * i] = true）。这样，最终的 primes 数组中储存的就是 (2, n] 区间内的所有素数。

找到的其它代码

#include
#include
#define maxn 1000
#define LL long long
using namespace std;

LL n,prime[maxn+5],cnt,f[maxn+5];
bool vis[maxn+5];

void pre_fir()
{
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
}
int main()
{
    scanf("%lld",&n);
    pre_fir();
    f[0]=1;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=prime[i];j<=n;j++)
        {
            f[j]+=f[j-prime[i]];
        }
    }
    printf("%lld\n",f[n]);
    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
const int M=1005;
int p[M];
long long dp[M];
bool check[M];
int n;
void in()
{
	scanf("%d",&n);
}
void get()
{
	check[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!check[i])p[++p[0]]=i;
		for(int j=1,t;j<=p[0];++j)
		{
			t=i*p[j];
			if(t>n)break;
			check[t]=1;
			if(i%p[j]==0)break;
		}
	}
}
void ac()
{
	get();
	dp[0]=1;
	for(int i=1;i<=p[0];++i)for(int j=0;j<=n;++j)
	if(j+p[i]<=n)dp[j+p[i]]+=dp[j];
	printf("%lld",dp[n]);
}
int main()
{
	in(),ac();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38