[算法]类似n sum个数的问题（DP）

题目

求和为target的数组元素组合数，含重复。

例：

输入

arr = { 1, 2, 3, 3, 4 } ，target = 6

输出 4

题解

dp[i][j]代表到数组第i-1个元素，目标和为j的组合数。

代码

package DP;

public class TargetSumCnt {

	public static void main(String args[]) {

		int[] arr = { 1, 2, 3, 3, 4 };

		int target = 6;

		int ans = targetSumCnt(arr, target);

		System.out.print(ans);

	}

	private static int targetSumCnt(int[] arr, int target) {

		int len = arr.length;

		int[][] dp = new int[len + 1][target + 1];// 到第i个元素（从1计），和为target的组合个数

		dp[0][0] = 1;

		for (int i = 1; i <= len; ++i) {

			for (int j = 0; j <= target; ++j) {

				if (arr[i - 1] > j) {

					dp[i][j] = dp[i - 1][j];

				} else {

					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]];

				}

			}

		}

		return dp[len][target];

	}

}

巴特西

[算法]类似n sum个数的问题（DP）

题目

题解

代码

最新文章

热门文章