[LintCode] k Sum [三维动态规划]

JeOam 发布于2019-08-14 15:31 / 2474人阅读

摘要：使用三维动规数组，表示从遍历到后找到的个元素之和为的情况的总数。操作如下首先，若第个元素，也就是，大于，那么从前个元素中取个元素令个元素之和为的所有情况和第个元素无关。因为，加上这个元素之后的不会影响已经遍历过的。

Problem

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

Note

这道题和Distinct Subsequence很像。
使用三维动规数组dp[i][j][t]，表示从0遍历到A[i]后找到的j个元素之和为t的情况的总数。最后返回从整个A数组找到的k个元素之和为target的情况总数即可。操作如下：
首先，若第i个元素，也就是A[i-1]，大于t，那么“从前i个元素中取j个元素令j个元素之和为t的所有情况”和第i个元素无关。也就是说dp[i][j][t] = dp[i-1][j][t]。而如果最后一个元素A[i-1] <= t，那么这个元素一定能带来一些不同的“从前i个元素中取j个元素令j个元素之和为t的情况”，但是，还要加上完全不考虑这个元素A[i-1]时的解的集合，也就是dp[i-1][j-1][t-A[i-1]]。因为，加上这个元素之后的dp[i][j-1][t-A[i-1]]不会影响已经遍历过的dp[i-1][j-1][t-A[i-1]]。

Solution

public class Solution {
    public int kSum(int A[], int k, int target) {
        int[][][] dp = new int[A.length+1][k+1][target+1];
        for (int i = 0; i <= A.length; i++) dp[i][0][0] = 1;
        //Super DP
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    dp[i][j][t] = dp[i-1][j][t];
                    if (A[i-1] <= t) dp[i][j][t] += dp[i-1][j-1][t-A[i-1]];
                }
            }
        }
        return dp[A.length][k][target];
    }
}

服务器托管海外云主机动态规划动态规划python java动态规划代码 java零钱动态规划

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65822.html

[LintCode/LeetCode] Check Sum of K Primes

Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...

lakeside 2019-08-16 12:37 评论0 收藏0
[LintCode] Submatrix Sum

摘要：原理是这样的先对矩阵的每个点到左顶点之间的子矩阵求和，存在新矩阵上。注意，代表的是到的子矩阵求和。说明从到行，从到列的子矩阵求和为，即相当于两个平行放置的矩形，若左边的值为，左边与右边之和也是，那么右边的值一定为。 Problem Given an integer matrix, find a submatrix where the sum of numbers is zero. Yo...

TesterHome 2019-08-14 15:22 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0
[LintCode] k Sum II [Backtracking]

摘要：当的大小为时，若也正好减小为，说明当前路径是正确的结果之一存入新的数组，再将放入。在循环递归之后，将中最后一个放入的元素删除，以在当前循环内继续替换和递归。 Problem Given n unique integers, number k (1

tabalt 2019-08-14 15:31 评论0 收藏0
[LintCode] Amicable Pair

Problem An amicable pair (m,n) consists of two integers m,n for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other. Given an integer k, find all...

mumumu 2019-08-15 13:38 评论0 收藏0