[LintCode] k Sum [三維動態規劃]

JeOam 發布于2019-08-14 15:31 / 2591人閱讀

摘要：使用三維動規數組，表示從遍歷到后找到的個元素之和為的情況的總數。操作如下首先，若第個元素，也就是，大于，那么從前個元素中取個元素令個元素之和為的所有情況和第個元素無關。因為，加上這個元素之后的不會影響已經遍歷過的。

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];
    }
}

云服務器 GPU云服務器動態規劃動態規劃python java動態規劃代碼 java零錢動態規劃

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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