Leetcode #377 动态规划逻辑题

Question

我一直在努力理解 LC #377 中显示的讨论解决方案之一。我不明白结果是如何增加的。我可以看到有一行：

result += combinations(nums, dp, target - nums[i])

这显然是递增结果，但是结果究竟是如何递增的？我所看到的是结果被初始化为 0 然后如果条件是则执行该行满意，所以不会行：

dp[target] = result

总是设置为 0?。真的很难理解，所以不胜感激。

代码：

class Solution {
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    Arrays.fill(dp, -1);
    dp[0] = 1;
    return combinations(nums, dp, target);
}

public int combinations(int[] nums, int[] dp, int target) {
    if (dp[target] != -1) {
        return dp[target];
    }
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            result += combinations(nums, dp, target - nums[i]);
        }
    }
    dp[target] = result;
    return result;
}

}

Answer 1

重点回复您关于 result 递增的问题。这是您提到的代码：

    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        if (target >= nums[i]) {
            result += combinations(nums, dp, target - nums[i]);
        }
    }
    dp[target] = result;

有一个 for 循环将 i 从 0 递增到 nums.length-1。对于每个这样的 i，如果满足此条件 (target >= nums[i])，则每次调用 combinations(nums, dp, target - nums[i]) 都会更新 result。您可以从签名中看到 combinations() returns 一个 int 值。

当达到 dp[target] = result 时，result 包含对 combinations().

的每次调用返回的值的总和

以下代码可能对您有所帮助。它计算 1 到 n 之间的偶数总数。我写它是为了匹配您 post 中使用的递归风格。希望对你有帮助。

public class SumDemo {
    int checkEven(int n) {
        return (n % 2 == 0) ? 1 : 0;
    }

    int countEven(int n) {
        int result = 0;
        for (int i = 1; i <=n; i++) {
            result += checkEven(i);
        }
        return result;
    }

    public static void main(String[] args) {
        SumDemo demo = new SumDemo();
        System.out.println(demo.countEven(10));
    }
}

Result:
5

(因为1到10之间有5个偶数(包括)): 2, 4, 6, 8, 10

Leetcode #377 动态规划逻辑题

Leetcode #377 Dynamic Programming Logic Question

java

dynamic-programming