动态规划-素数侣伴
动态规划--素数伴侣
素数伴侣：
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，
从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，存到int array[]
如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，
能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
这里利用动态规划解题:
我们利用倒叙解题：
dp[i]表示i--n所具有的最大素数对数。
当两个数arr[i]+arr[j]之和为素数时，此时满足dp[i]+dp[j]=dp[i+1]+dp[j+1]+1;
当不是素数时，此时满足dp[i] = dp[i+1];
核心代码如下：
素数伴侣：
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，
从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，存到int array[]
如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，
能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
这里利用动态规划解题:
我们利用倒叙解题：
dp[i]表示i--n所具有的最大素数对数。
当两个数arr[i]+arr[j]之和为素数时，此时满足dp[i]+dp[j]=dp[i+1]+dp[j+1]+1;
当不是素数时，此时满足dp[i] = dp[i+1];
核心代码如下：
int count = 0
//用来保存每个i对应的素数对，然后依次和之前的进行比较求出最大值
for(int i=n-2;i>-1;i--){
for(int j=n-1;j>i;j--){
//依次循环j，找到对应的每个i最大的素数对。
count = IsPrime(arr[i]+arr[j])
?dp[i+1]+dp[j+1]-dp[j-1]+1:dp[i+1];
//这里有一个需要注意的地方，就是我们代码中求的公式为
//dp[i]+dp[j-1]=dp[i+1]+dp[j+1]+1;
dp[i]=Math.max(count,dp[i]);
}
}
//由于是倒叙排序，因此dp[0]应该是动态规划最后求出来的最大值
System.out.println(dp[0]);