第一道题:数组素数拆分
第一组测试用例:[1,1,1],输出:0
第二组测试用例:[5,3,7],输出:6
思路:先找出数组中的最大值max,然后根据max求出max之前的所有素数放入到一个list中,然后再利用动态规划来做。
定义状态:dp[i]表示数字i能够拆分的最多的素数个数
状态转移:对list中所有小于i的素数j,有这样的转移公式dp[i]=Math.max(dp[i],dp[i-j])
初始化:dp[0]=0,dp[1]=0;
import java.util.*; public class Main { public static void main(String[] args) { //设置两组测试用例 int[] a1 = {3, 5, 7}; //期待输出是6 int[] a={1,1,1}; //期待输出是0 int max = 0; //找出最大值 for (int i : a) max = Math.max(max, i); //找出所有的素数 ArrayList<Integer> list = new ArrayList<>(); for (int i = 2; i <= max; i++) { if (judgeSushu(i)) list.add(i); } //这是一个动态规划 int[] dp = new int[max + 1]; dp[0] = 0;//这个是由其他转移过来的 dp[7-7]=dp[0]=1 dp[1] = 0; //计算dp状态转移 for (int i = 3; i <= max; i++) { for(int n:list) { if(n>i) break; else dp[i]=Math.max(dp[i],dp[i-n]+1); } } //统计数组中所有数的拆分成的最大素数个数 int count=0; for(int i=0;i<a.length;i++) count+=dp[a[i]]; System.out.println("总共有"+count+"个素数"); } //判断一个数是否是素数 public static boolean judgeSushu(int n) { for(int i=2;i<=Math.sqrt(n);i++) if(n%i==0) { return false; } return true; } }
全部评论
(3) 回帖