[LintCode] k Sum [三維動態(tài)規(guī)劃]

JeOam 發(fā)布于2019-08-14 15:31 / 2608人閱讀

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

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很像。
使用三維動規(guī)數(shù)組dp[i][j][t]，表示從0遍歷到A[i]后找到的j個元素之和為t的情況的總數(shù)。最后返回從整個A數(shù)組找到的k個元素之和為target的情況總數(shù)即可。操作如下：
首先，若第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]]不會影響已經(jīng)遍歷過的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云服務器動態(tài)規(guī)劃動態(tài)規(guī)劃python java動態(tài)規(guī)劃代碼 java零錢動態(tài)規(guī)劃

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.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

摘要：復雜度思路參考的思路，對于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價值。對于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個值的最大值。 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]

摘要：當?shù)拇笮闀r，若也正好減小為，說明當前路徑是正確的結(jié)果之一存入新的數(shù)組，再將放入。在循環(huán)遞歸之后，將中最后一個放入的元素刪除，以在當前循環(huán)內(nèi)繼續(xù)替換和遞歸。 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