剑指 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]));
}
- 组合总和 Ⅳ
难度
给你一个由 不同 整数组成的数组 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);
}
}