原文链接：https://blog.csdn.net/qq_39355828/article/details/121114818 (opens new window) 剑指 Offer II 091. 粉刷房子

难度

中等

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]

输出: 10

解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。

最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]

输出: 2

动态规划，每一个房子的颜色只与前一个房子房子有关

public int minCost(int[][] costs) {
    int[][] dp=new int[costs.length][3];
    //第一个房子
    for(int i=0;i<3;i++)
        dp[0][i]=costs[0][i];//第一列，初始值
    for(int i=1;i<costs.length;i++)
    {   //转移方程
        dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i][0];//当前涂得是红色，则之前的只能涂蓝色，或者绿色
        dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i][1];//当前涂的是蓝色
        dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+costs[i][2];//当前涂的是绿色
    }
    //最后返回最后一行中的最小花费
    return Math.min(dp[costs.length-1][0],Math.min(dp[costs.length-1][1],dp[costs.length-1][2]));
    }

1. 组合总和 Ⅳ

难度

给你一个由 不同 整数组成的数组 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)

请注意，顺序不同的序列被视作不同的组合。

动态规划，dp[i]表示组合成i所有的组合数

标题

public int combinationSum4(int[] nums, int target)
    {
        //定义动态数组
    int[] dp=new int[target+1];
    //初始化变量
    dp[0]=0;
    //从1到当前值，所有的组合情况
    for(int i=1;i<=target;i++)
    {   //对可以有的选择进行遍历
        for(int num:nums)
        {
            if(num<=i)
                dp[i]=dp[i]+dp[i-num];
        }
    }
    return dp[target];
    }

剑指 Offer II 084. 含有重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]

输出：

[[1,1,2],

[1,2,1],

[2,1,1]]

示例 2：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

List<List<Integer>>lists=new ArrayList<>();
    List<Integer>list=new ArrayList<>();
    Set<List<Integer>>set=new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums)
    {
    for(int i=0;i<nums.length;i++)
    {
        list.add(nums[i]);
    }
    dfs(list,0);
    return lists;
    }
    public void dfs(List<Integer>list,int i)
    {
        if(i>=list.size()&&set.add(new ArrayList<>(list)))
            lists.add(new ArrayList<>(list));
            //交换再返回
        for(int j=i;j<list.size();j++)
        {

            Collections.swap(list,j,i);
            dfs(list,i+1);
            Collections.swap(list,j,i);

        }
    }

剑指 Offer II 081. 允许重复选择元素的组合

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = [2,3,6,7], target = 7

输出: [[7],[2,2,3]]

示例 2：

输入: candidates = [2,3,5], target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]

public List<List<Integer>> combinationSum(int[] candidates, int target)
    {
        List<List<Integer>>ans=new ArrayList<>();
        List<Integer>conbine=new ArrayList<>();
        dfs(candidates,ans,conbine,0,target);
        return ans;
    }
    public  void dfs(int[] candidates,List<List<Integer>>ans,List<Integer>conbine,int index,int target)
    {   //已经遍历到最后，仍不满足条件，应该返回
        if(index==candidates.length)
            return;
        //当前的可以满足条件，则应该加入到数组中，并且返回，不返回可能会有重复
        if(target==0)
        {
            ans.add(new ArrayList<>(conbine));
            return;
        }
        //不选择当前的数字
        dfs(candidates,ans,conbine,index+1,target);
        //可以选择当前的额数字
        if(target>=candidates[index])
        {   //先将当前的数字加入
            conbine.add(candidates[index]);
            //进行遍历，此时剩下的目标值就是target减去当前值
            dfs(candidates,ans,conbine,index,target-candidates[index]);
            //将加入的数字移除，进行回溯
            conbine.remove(conbine.size()-1);
        }
    }