今天仍然是DP的学习，但第一个题显然用回溯更加简单！
1.目标和（力扣494）
本题通过一个数组寻找目标和，由于可以任意在元素前加加减号，则利用回溯遍历所有情况，从第一个数开始遍历添加加号和减号的情况。
int res = 0;
public int findTargetSumWays(int[] nums, int target) {
search(nums,target,0);
return res;
}
public void search(int[] nums, int target, int index){
if(index == nums.length)
{
if(target == 0)
res++;
return;
}
search(nums,target-nums[index],index+1);
search(nums, target+nums[index],index+1);
}
2.一和零（力扣474）
本题可以抽象为三维01背包问题，背包容量限制从一个变为两个，想通了也就没那么难理解了。把0和1的个数限制作为背包容量的两个限制，把字符串数组中的字符串抽象成物品，价值即为个数（放（1）与不放（0）），最后就能得到最大子集长度。
public int findMaxForm(String[] strs, int m, int n) {
//看作三维动态规划问题，背包从之前一个限制变为两个限制，dp[i][j][k]表示当前第i个元素的情况下背包两个限制容量为j、k时strs最大子集的大小
int[][][] dp = new int[strs.length][m+1][n+1];
//记录0和1的数量
int zeronum = 0;
int oneNum = 0;
//初始化i=0的情况
for (int j = 0; j < strs[0].length(); j++) {
if(strs[0].charAt(j) == '0')
zeroNum++;
else
oneNum++;
}
//仍然是初始化，比01背包问题多了一维
for (int j = zeroNum; j <= m; j++) {
for (int k = oneNum; k <= n; k++) {
dp[0][j][k] = 1;
}
}
//由于i=0已经初始化过，直接从i=1开始，也就是strs中第二个元素开始放
for (int i = 1; i < strs.length; i++) {
zeronum = 0;
oneNum = 0;
for (int j = 0; j < strs[i].length(); j++) {
if(strs[i].charAt(j) == '0')
zeroNum++;
else
oneNum++;
}
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
//背包放不下
if(j < zeronum || k < oneNum)
dp[i][j][k] = dp[i-1][j][k];
//背包放得下
else
dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
}
}
}
return dp[strs.length-1][m][n];
}
3.零钱兑换2（力扣518）
完全背包+组合问题，一维数组解决，需要提前初始化（内层循环从前向后了，之前01背包问题不用是因为从后往前遍历）先遍历物品再遍历背包容量，内层循环需要从前向后遍历，一个物品可以放很多次。注意组合问题dp[j] += dp[j - coins[i]];
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
//初始化
dp[0] = 1;
for (int i = 0; i < coins.length; i++) { // 遍历物品
for (int j = 0; j <= amount; j++) { // 遍历背包容量
if(j >= coins[i])
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
4.组合总和4（力扣377）
完全背包+排列问题，一维数组解决，和上题相同，需要初始化，从前往后遍历，但上题是组合问题，外层循环遍历物品内层循环遍历容量，本题是排列问题外层循环遍历容量内层循环遍历物品。排列问题同样dp[j] += dp[j-nums[i]]。
public 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]];
}
}
return dp[target];
}
5.零钱兑换（力扣322）
本题首先分析清楚需要最小的值，因此初始化时除了第一个数都应该为最大数，然后遍历时更新最小值，则最后就能得到答案。对于动态规划题，只要能抽象出来，大体都一样，主要是遍历顺序和递推式
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
for (int j = 0; j <= amount; j++) {
if(j>=coins[i] && dp[j - coins[i]] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
}
}
if(dp[amount] == Integer.MAX_VALUE)
return -1;
return dp[amount];
}
6.完全平方数（力扣279）
要明确背包问题中的容量是多少、物品是什么，本题容量是n，物品是小于等于根号n的数，求将物品装进背包所需要最小的物品数。要学会把问题抽象。
public int numSquares(int n) {
int[] dp = new int[n+1];
//要找最小值，填充最大值
Arrays.fill(dp,Integer.MAX_VALUE);
//初始化
dp[0] = 0;
//先遍历物品，最多到sqrt(n)
for (int i = 0; i * i <= n; i++) {
//再遍历容量
for (int j = 0; j <= n ; j++) {
//注意当dp[j-i*i]就是最大值时没有比较意义，若不加这个条件就会使dp[j-i*i]+1为最小值，出错
if(j >= i * i && dp[j-i*i] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j],dp[j-i*i]+1);
}
}
return dp[n];
}
7.打家劫舍（力扣198）
本题采用动态规划的方法，dp[i]表示到第i个元素能获得的最大收益，而最大收益在于取前一个还是取前一个的前一个和当前元素。
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
8.打家劫舍2（力扣213）
本题与上题唯一的不同在于首尾相接，即不能同时偷第一个和最后一个，就把整体分为两段，分别包含头和尾。再用上题的解决方案做。
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
if(nums.length == 1)
return nums[0];
int res1 = range(nums,0,nums.length-1);
int res2 = range(nums,1,nums.length);
return Math.max(res1, res2);
}
public int range(int[] nums, int start, int end){
if(end-start == 1)
return nums[start];
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start+1] = Math.max(nums[start],nums[start+1]);
for (int i = start+2; i < end; i++) {
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[end-1];
}
9.买卖股票的最佳时机（力扣121）
使用贪心，让买的时候尽量低，然后取区间最大值。
public int maxProfit(int[] prices) {
//用贪心，尽可能让右边的小，取区间内最大值
int low = Integer.MAX_VALUE;
int res = 0;
for (int i = 0; i < prices.length; i++) {
low = Math.min(low,prices[i]);
res = Math.max(res,prices[i]-low);
}
return res;
}
*10.最长递增子序列（力扣300）
本题用动态规划求最长递增子序列，dp[i]表示第i个位置前（包括第i个位置）构成的最长递增子序列的长度，由于中间元素可以跳过，则需要从下标0比较到i-1。递推公式为dp[i] = Math.max(dp[i],dp[j]+1)。
public int lengthOfLIS(int[] nums) {
if(nums.length == 1)
return 1;
//动态规划：dp[j]表示到第j个位置时，最长递增子序列的长度
int[] dp = new int[nums.length];
// dp[0] = 1;由于每个元素都有可能作为开始，则每个元素初始值都是1
Arrays.fill(dp,1);
int max = 0;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
//与之前的每一个都比（因为中间的可以删除）
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
//记录最长的
max = Math.max(max,dp[i]);
}
return max;
}
11.最长连续递增序列（力扣674）
本题与上题不同，需要连续，则既可以用贪心记录最大值，也可以用动态规划记录每个位置的值后取最大。相对简单。
贪心：
public int findLengthOfLCIS(int[] nums) {
if(nums.length == 1)
return 1;
int count = 1;
int res = 0;
for (int i = 1; i < nums.length; i++) {
if(nums[i]>nums[i-1])
count++;
else
count = 1;
res = Math.max(res,count);
}
return res;
}
动态规划：
public int findLengthOfLCIS(int[] nums) {
if(nums.length == 1)
return 1;
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int max = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
if(nums[i] > nums[i-1]){
dp[i] = dp[i-1]+1;
}
max = Math.max(max,dp[i]);
}
return max;
}
12.最长重复子数组（力扣718）
本题利用动态规划，关键点在于，两数组值相等时有dp[i][j] = dp[i-1][j-1] + 1，其中dp[i][j]表示以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度。
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
int max = Integer.MIN_VALUE;
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if(nums1[i-1] == nums2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
max = Math.max(max,dp[i][j]);
}
}
return max;
}
