• 代码随想录笔记_动态规划_377组合总和IV


    代码随想录二刷笔记记录

    LC377.组合总和IV


    题目

    完全背包

    给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

    题目数据保证答案符合 32 位整数范围。

    示例 1:

    输入:nums = [1,2,3], target = 4
    输出:7
    解释:
    所有可能的组合为:
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    请注意,顺序不同的序列被视作不同的组合。

    示例 2:

    输入:nums = [9], target = 3
    输出:0


    思路分析

    分析:由题中示例1可知,本题所求为排列个数

    回顾 LC 518

    组合不强调元素间的顺序,排列强调元素间的顺序

    因为本题只求排列个数,而不是返回所有排列,因此,采用 dp 而不用采用回溯。

    动态规划五部曲

    1.确定dp数组及其下标的含义

    dp[j] :组成目标正整数 j 的排列个数为 dp[j]
    目标正整数即为背包容量 j,也可以理解为
    表示由背包容量j,放置nums中的元素,组成所有可能的排列 dp[j]
    
    • 1
    • 2
    • 3

    2.确定递推公式
    由494.目标和,可知求组合的递推公式

    dp[j] += dp[j - nums[i]]
    所有的 dp[j - nums[i]] 累加,就是 nums[i] 所有可能的组合数量
    
    • 1
    • 2

    3.初始化

    背包组合问题,dp[0]初始化为1即可,避免累加为0的情况出现

    4.遍历顺序

    注意,示例1所求的组合包含了(1,1,2),(1,2,1) ,说明题目要求的是排列(顺序不同则算作一种新的组合)。

    回顾518可知,排列需要先遍历背包,后遍历物品

    for(int j = 0;j <= target;j++){//遍历背包容量j
    	for(int i = 0;i < nums.length;i++){//遍历物品i
    		//物品超过背包容量,则不需要添加
    		if(j >= nums[i]){
    			dp[j] += dp[j - nums[i]];
    		}
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5.推演分析

    以nums[1,2,3] , target = 4 为例

    请添加图片描述

    背包j/物品iinit物品0物品1物品2
    01111
    10111
    20122
    30134
    40157

    代码实现

    完整代码实现

    public static int combinationSum4(int[] nums, int target) {
            //初始化
            int[] dp = new int[target+1];
            dp[0] = 1;
            //遍历
            for(int j = 0;j <= target;j++){//先遍历背包
                for(int i = 0;i < nums.length;i++){//遍历物品
                    if(j >= nums[i]){
                        dp[j] += dp[j - nums[i]];
                        System.out.print(dp[j] + " ");
                    }
                }
                System.out.println();
            }
            return dp[target];
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

  • 相关阅读:
    2023年【上海市安全员C证】考试及上海市安全员C证找解析
    Verilog:【7】超详细WaveDrom教程,时序图绘制利器,看这一篇就够了。
    QT学习管理系统
    【UCIe】UCIe 数据完整性
    HTTP与HTTPS
    力扣------路径总和 III
    Codeforces Global Round 21 D. Permutation Graph
    多线程【thread】【queue储存、锁】【2】
    第04章 逻辑架构【1.MySQL架构篇】【MySQL高级】
    Vue实现多角色登录,Vue-Router路由守卫控制权限页面
  • 原文地址:https://blog.csdn.net/Erik_Ying/article/details/126157256