力扣 中等 377.组合总和-题解

本质是爬楼梯,相当于每次往上爬 nums[i]步

本题和爬楼梯是一个思路,只不过我们每次从 nums 中选一个数,作为往上爬的台阶数,问爬 target 个台阶有多少种方案。爬楼梯那题可以看作 nums=[1,2],因为每次只能爬 1 个或 2 个台阶。

代码如下:

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;  // 参考爬楼梯
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i) {
                    dp[i] += dp[i - x];
                }
            }
        }
        return dp[target];
    }
}
上一篇:Java Web项目实战:从零基础到项目开发全流程


下一篇:<Project-11 Calculator> 计算器 0.4 公制单位转换器 Metric Units Converter HTML JS