求解数组凑和问题
给定一个数组，给一个数a。从数组里拿元素求和能组成a,有几种方案
2017-09-13 16:21 已编辑 吉林大学 安全工程师
关注
全部评论
Thare
淘天集团_技术专家
动态规划 import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int sum = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = scanner.nextInt();
}
long result = process(arr, n, sum);
System.out.println(result);
}
}
private static long process(int[] arr, int n, int sum) {
long[][] dp = new long[n][sum + 1];
int i, j;
for (i = 0; i < n; ++i) {
dp[i][0] = 1;
}
if (arr[0] <= sum) {
dp[0][arr[0]] = 1;
}
for (i = 1; i < n; ++i) {
for (j = 1; j <= sum; ++j) {
dp[i][j] = dp[i-1][j];
if (j - arr[i] >= 0) {
dp[i][j] += dp[i - 1][j - arr[i]];
}
}
}
return dp[n-1][sum];
}
}
yanxutao
西北工业大学 Java
// 动态规划
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = sc.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
long[][] dp = new long[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int j = 1; j <= sum; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (a[i] <= j) {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[n][sum]);
}
}
whuzz
武汉大学 算法工程师
双指针?
相关推荐
点赞 评论 收藏
分享
腾讯云智研发一面203人在聊
查看6道真题和解析 
点赞 评论 收藏
分享