文章目錄

• 題目描述
• 解析
• • 記憶化搜索
  • • 代碼
  • 無限背包
  • • 代碼
• thanks for reading！

題目描述

解析

很好的題

記憶化搜索

我一開始的思路就是記憶化搜索
為了不重復(fù)，搜索的時候規(guī)定拆出來一個數(shù)A后一會不能再拆比A更小的了
這樣就不難寫了
（忽略我n^2的素數(shù)篩法，反正數(shù)據(jù)一點(diǎn)點(diǎn)大）
線性篩在這里

代碼

#include<bits/stdc++.h> using namespace std; const int N=3e6+100; #define ll long long int n; int prime[N],m; bool sushu(int x){int ans=0;for(int i=1;i<=x;i++){if(x%i==0) ans++;}return ans==2; } void solve(){for(int i=2;i<=200;i++){if(sushu(i)) prime[++m]=i;} }ll dp[250][250]; ll find(int x,int k){if(dp[x][k]) return dp[x][k];if(x==0) return 1;if(x<0||x==1) return 0;ll res=0;for(int j= k;j<=m&&prime[j]<=x;j++){res+=find(x-prime[j],j);}return dp[x][k]=res; }int main(){solve(); while(scanf("%d",&n)!=EOF){printf("%lld\n",find(n,1));}return 0; } /* 12 21 31 40 49 58 69 79 90 101 15 */

但這并不是最好的做法

無限背包

這題可以轉(zhuǎn)化為：

給你一些數(shù)（也就是那些質(zhì)數(shù)），然后問你組合成給定數(shù)值的方案數(shù)

這就是那個硬幣方案的題了
用背包可以非常容易的切掉
而且時間復(fù)雜度應(yīng)該比記搜好（記搜的那個復(fù)雜度有點(diǎn)玄。。。）

代碼

都說到這份上了還要什么代碼
（絕對不是我懶得敲）

thanks for reading！

總結(jié)

以上是生活随笔為你收集整理的质数和分解（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。