前言
动态规划也是重点啊，所以多找点题目写写，基本都是啥卡的
有的太简单的弱智题目就不放这了哈
63. 不同路径 II - 力扣（LeetCode）
有障碍了
区别就是在递推公式要加上判断条件，以及如果障碍在第一行或者第一列的时候，初始化的问题
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
//如果在起点或终点出现了障碍，直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
}
}
return dp[m - 1][n - 1];
}
}96. 不同的二叉搜索树 - 力扣（LeetCode）
一开始尝试找规律没找到
思路
背包问题
01背包问题dp[i][j]是什么：0-i的物品放大哦容量为j的背包的最大价值
二维数组：**dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);**
换成一维就是： dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
一维01背包必须先遍历物品
然后遍历背包时是倒序便利
套路：
//先遍历物品，再倒序遍历背包
for(int i=0;i<weight.length;i++)
{
for(int j=sumweight;j>=weight[i];j--)
{
dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]);
}
}有时候weight和value是同一个数组
而完全背包问题，如果是纯完全背包问题，无所谓遍历顺序
如果是装满背包有多少种方法，要分是排列数还是组合数：组合数：先物品，排列数：先背包
完全背包问题套路：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量，因为是无限取，所以可以正序遍历
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//先背包，再物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}416. 分割等和子集 - 力扣（LeetCode）
就是给你物品列表，价值就是具体的数，然后容量也没确定，反正就是看你能不能使价值等于所有数加起来的/2
0-1背包问题，因为每个数只能用一次
卡尔的思路是重量就等于价值，这样的好处是什么，就是背包的容量是可以被确定的
class Solution {
public boolean canPartition(int[] nums) {
int values=0;
for(int i=0;i<nums.length;i++)
{
values+=nums[i];
}
if(values%2!=0)return false;
values/=2;//目标价值
int []dp=new int[values+1];//背包最大就是和价值相同
for(int i=0;i<nums.length;i++)
{
for(int j=values;j>=nums[i];j--)
{
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[values]==values;
}
}1049. 最后一块石头的重量 II - 力扣（LeetCode）
这道题目等价于什么：把数组分为两部分，让两部分的差尽可能相等或者小，那么不就和上一题一样么
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i:stones)
{
sum+=i;
}
int target=sum/2;
int[]dp=new int[1501];
for(int i=0;i<stones.length;i++)
{
for(int j=target;j>=stones[i];j--)
{
dp[j]=Math.max(dp[j], dp[j-stones[i]]+stones[i]);
}
}
return sum-2*dp[target];
}494. 目标和 - 力扣（LeetCode）
思路：转化为背包问题，分为+集合和-集合，最后结果就是sum=＋集合加上-集合
target=＋集合减去-集合
然后得出，＋集合要等于（tartget+sum）/2
这种装满背包有多少种方法的递推公式：dp[j]+=dp[j-numbers[i]]，dp[j]为装满容量为j的背包有多少种方法
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int num:nums)
{
sum+=num;
}
if((sum+target)%2!=0)return 0;
if(target<0&&sum<-target)return 0;
int left=(sum+target)/2;
int[]dp=new int[left+1];
dp[0]=1;//根据题目推导的
for(int i=0;i<nums.length;i++)
{
for(int j=left;j>=nums[i];j--)
{
dp[j]+=dp[j-nums[i]];
}
}
return dp[left];
}518. 零钱兑换 II - 力扣（LeetCode）
这就到了完全背包问题
有了目标和的基础，做这个不难
//这里面coins就是物品，然后价值和重量也是相等的，就是coins的数值，然后总容量就是amount
//dp[j]:容量为j有多少种凑法
//地推：dp[j]+=dp[j-weight[i]]
public int change(int amount, int[] coins) {
int []dp=new int[amount+1];
dp[0]=1;//当容量为0只有一种，那就是什么也不装
for(int i=0;i<coins.length;i++)
{
for(int j=coins[i];j<=amount;j++)
{
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}322. 零钱兑换 - 力扣（LeetCode）
零钱兑换2是问有多少种凑法，这个是问题最少硬币个数
硬币是无线的，那么也是一个完全背包问题
看我一开始写的：
//dp[j]为容量为j的背包，装满他的最少硬币个数
//这题目也是一样，重量等于价值，就是coins【i】
//递推公式：dp[j],dp[j-coins[i]]推出，但是还得保证dp[j-conis[i]]的可以凑成的
//初始化：dp[0]=0;
public int coinChange(int[] coins, int amount) {
int[]dp=new int[amount+1];
for(int i=0;i<coins.length;i++)
{
for(int j=coins[i];j<=amount;j++)
{
if(dp[j-coins[i]]!=0)
{
dp[j]=dp[j-coins[i]]+1;
}
}
}
return dp[amount];
}我漏了哪些思考：应该取最小的dp[j]，因为双循环你的dp[j]肯定会比较不止一次啊
所以修改：
//dp[j]为容量为j的背包，装满他的最少硬币个数
//这题目也是一样，重量等于价值，就是coins【i】
//递推公式：dp[j],dp[j-coins[i]]推出，但是还得保证dp[j-conis[i]]的可以凑成的
//初始化：dp[0]=0;
public int coinChange(int[] coins, int amount) {
int[]dp=new int[amount+1];
for(int i=0;i<dp.length;i++)
{
dp[i]=Integer.MAX_VALUE;//初始化成最大值，防止被覆盖
}
dp[0]=0;
for(int i=0;i<coins.length;i++)
{
for(int j=coins[i];j<=amount;j++)
{
if(dp[j-coins[i]]!=Integer.MAX_VALUE)
{
dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]);
}
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];//还等于最大值说明凑不出来
}279. 完全平方数 - 力扣（LeetCode）
这个一眼完全背包问题啊
public int numSquares(int n) {
int max=Integer.MAX_VALUE;
int[]dp=new int[n+1];
Arrays.fill(dp, max);
dp[0]=0;
for(int i=1;i*i<=n;i++)
{
for(int j=i*i;j<=n;j++)
{
dp[j]=Math.min(dp[j], dp[j-i*i]+1);//一定能凑成，所以不需要判断了
}
}
return dp[n];
}139. 单词拆分 - 力扣（LeetCode）
可以重复使用，一眼完全背包啊吗，因为这里其实是排列数，就是你的字符得有顺序，所以先遍历背包
//也是背包问题背包就就是给的String s，
//物品列表就是wordDICT
//然后可以重复使用，说明是完全背包问题
//但是单词有顺序，是排列数，所以是先遍历背包
public boolean wordBreak(String s, List<String> wordDict) {
boolean []dp=new boolean[s.length()+1];//dp[i]:长度为i能否背凑成
dp[0]=true;
for(int i=0;i<=s.length();i++)
{
for(int j =0;j<i&&!dp[i];j++)//遍历物品，注意，这里是遍历字符串并且判断他是不是物品
{
if(dp[j]&&wordDict.contains(s.substring(j,i)))
{
dp[i]=true;
}
}
}
return dp[s.length()];
}打家劫舍和股票问题
198. 打家劫舍 - 力扣（LeetCode）
//每个房间都有两个选择：偷和不偷
//dp[i]:走到这个房间能偷到的最高金额
//偷：dp[i]=dp[i-2]+nums[i]
//不偷：dp[i]=dp[i-1]
public int rob(int[] nums) {
int []dp=new int[nums.length];
dp[0]=nums[0];
if(nums.length==1)return dp[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]);
}
int res=Integer.MIN_VALUE;
return dp[nums.length-1];
}213. 打家劫舍 II - 力扣（LeetCode）
比上一题多了一个条件,首尾相邻
其实就是把打家劫舍抽象了
class Solution {
//区别就是和上一题相比，这一题最后一个和第一个是相邻的，那么我们直接分两种情况，第一件偷和第一间不偷
public int rob(int[] nums) {
if(nums.length==0)return 0;
if(nums.length==1)return nums[0];
int v1=solve(nums, 0, nums.length-2);//偷第一件，那最后一件不能投
int v2=solve(nums, 1, nums.length-1);//不偷异地检
return v1>v2?v1:v2;
}
public int solve(int[] nums,int l,int r) {
if(l==r)return nums[l];
int []dp=new int[nums.length];
dp[l]=nums[l];
dp[l+1]=Math.max(nums[l], nums[l+1]);
for(int i=l+2;i<=r;i++)
{
dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[r];
}
}121. 买卖股票的最佳时机 - 力扣（LeetCode）
有一说一这题是算在贪心算法里
//维护当前的最小值，和当前的最大利润，计算本次利润和最大利润比较即可
public int maxProfit(int[] prices) {
int []res=new int[prices.length];
int minvalue=Integer.MAX_VALUE;
int maxprofit=Integer.MIN_VALUE;
for(int i=0;i<prices.length;i++)
{
res[i]=prices[i]-minvalue>0?prices[i]-minvalue:0;
minvalue=Math.min(prices[i], minvalue);
maxprofit=Math.max(res[i], maxprofit);
}
return maxprofit;
}但是为了后面的不能用贪心算法解的题目呢，还是得会动态规划怎么写
那么这就涉及到二维dp了dp[i][0]表示第i天持有股票,dp[i][1]表示第i天不持有股票
public int maxProfit(int[] prices) {
int[][]dp=new int[prices.length][2];
dp[0][0]=-prices[0];//第一天持有，那么直接减去数值
dp[0][1]=0;
for(int i=1;i<prices.length;i++)
{
dp[i][0]=Math.max(dp[i-1][0], -prices[i]);//持有，那么要么是今天买，要么是之前买的
dp[i][1]=Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);//不持有，要么是卖了，要么是没买
}
return dp[prices.length-1][1];//你最后肯定得卖掉
}122. 买卖股票的最佳时机 II - 力扣（LeetCode）
比上一题多了的部分就是可以多次购买出售了
但是这题用动态规划理解太复杂了，我们直接上贪心算法：只要今天股价比昨天高，就交易
public int maxProfit(int[] prices) {
int len=prices.length;
if(len<2)
return 0;
int res=0;
for(int i=1;i<len;i++)
{
int diff=prices[i]-prices[i-1];
if(diff>0)
{
res+=diff;
}
}
return res;
}因为你不限制交易次数啊，所以我们可以把所有的利润空间全部拿下
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
这题你就不能用贪心了，只能老老实实动态规划了，草!!!!
多维动态规划的关键在于：拆分状态
这里就能拆成四个状态：
第一次持有，第一次不持有，第二次持有，第二次不持有
分别对应dp[i][1][2][3][4]
那么递推公式呢
dp[i][1]第一次持有，所以要么是今天买了，-prices[i]，要么是之前买过了dp[i-1][1]
dp[i][2]第一次不持有，要么是今天卖了，dp[i-1][1]+price[i]，要么是啥也没干，dp[i-1][2]
dp[i][3]第二次持有，要么是今天买了dp[i-1][2]-prices[i]，要么啥也没干dp[i-1][3]
dp[i][4]第二次不持有，要么是今天卖了dp[i-1][3]+prives[i]，要么啥也没干，dp[i-1][4]总结之后易得：
public int maxProfit(int[] prices) {
int len=prices.length;
int[][]dp=new int[len][5];
dp[0][1]=-prices[0];
dp[0][3]=-prices[0];//初始化
for(int i=1;i<prices.length;i++)
{
dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]);
dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
}
return dp[len-1][4];
}188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
至多k次交易，其实根据上一题找规律就行了
买卖两次我们定义是4个状态，5的数组，那么k次就是2k个状态，2k+1大的数组呗
public int maxProfit(int k, int[] prices) {
if(prices.length==0)return 0;
int len=prices.length;
int[][]dp=new int[len][2*k+1];
for(int i=1;i<k*2;i+=2)
{
dp[0][i]=-prices[0];//初始化，奇数(第i次持有)全部初始化成-prices[0]
}
for(int i=1;i<len;i++)//找规律一个一个填吧
{
for(int j=0;j<k*2-1;j+=2)//对每一天，去计算k个状态，j始终为偶数
{
dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);//j+1为奇数，那就是持有
dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);//不持有
}
}
return dp[len-1][k*2];
}序列问题
300. 最长递增子序列 - 力扣（LeetCode）
class Solution {
//重点是什么，你要和你前面的所有子序列比
public int lengthOfLIS(int[] nums) {
int []dp=new int[nums.length];
Arrays.fill(dp, 1);
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[j]+1,dp[i]);
}
}
}
int res=0;
for(int i=0;i<nums.length;i++)
{
res=Math.max(res, dp[i]);
}
return res;
}
}674. 最长连续递增序列 - 力扣（LeetCode）
//要连续了，那就是只用和前面一个比就行了
public int findLengthOfLCIS(int[] nums) {
int[]dp=new int[nums.length];
Arrays.fill(dp, 1);
for(int i=1;i<nums.length;i++)
{
if(nums[i]>nums[i-1])
{
dp[i]=dp[i-1]+1;
}else
{
dp[i]=1;
}
}
int res=0;
for(int i=0;i<dp.length;i++)
{
res=Math.max(res, dp[i]);
}
return res;
}718. 最长重复子数组 - 力扣（LeetCode）
//dp[i][j]表示i-1,j-1为结尾的，两个的最长重复子数组
//地推公式：如果相等，那么等于dp[i-1][j-1]+1，因为是子数组，所以无需其他情况
public int findLength(int[] nums1, int[] nums2) {
int [][]dp=new int[nums1.length+1][nums2.length+1];
int res=0;
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;
}
res=Math.max(res,dp[i][j]);
}
}
return res;
}1143. 最长公共子序列 - 力扣（LeetCode）
你看是不是就是上一题把子数组换成子序列
这种问题统统表示为i-1.j-1为结尾的，这样就不用初始化了
public int longestCommonSubsequence(String text1, String text2) {
int len1=text1.length();
int len2=text2.length();
int [][]dp=new int[len1+1][len2+1];
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(text1.charAt(i-1)==text2.charAt(j-1))
{
dp[i][j]=dp[i-1][j-1]+1;
}else
{
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}53. 最大子数组和 - 力扣（LeetCode）
//子数组，那就是连续的序列
//
public int maxSubArray(int[] nums) {
int[]dp=new int[nums.length];
dp[0]=nums[0];
if(nums.length==1)
{
return dp[0];
}
int res=dp[0];
for(int i=1;i<nums.length;i++)
{
dp[i]=Math.max(dp[i-1]+nums[i], nums[i]);
res=Math.max(res, dp[i]);
}
return res;
}72. 编辑距离 - 力扣（LeetCode）
动态规划核心：分割状态
我们的思路是只对一个进行删除修改操作，不做添加,因为对一个加相当于对另一个减
//dp[i][j]为i-1，j-1转换的最少操作次数
//那我们就是删除修改
//删除：可以对1也可以对2 ，修改对谁都是一样的
//所以 是三种状态
//删除1：那么就变成了dp[i-1][j]+1,删除2：dp[i][j-1]+1,修改:dp[i-1][j-1]+1
//那就行了，一股闹比较谁最小就行了
public int minDistance(String word1, String word2) {
int m=word1.length();
int n=word2.length();
int[] []dp=new int[m+1][n+1];
for(int i=1;i<=m;i++)
{
dp[i][0]=i;
}
for(int j=1;j<=n;j++)
{
dp[0][j]=j;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(word1.charAt(i-1)==word2.charAt(j-1))
{
dp[i][j]=dp[i-1][j-1];//相等就和之前一样啊
}else
{
dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j], dp[i-1][j-1]))+1;
}
}
}
return dp[m][n];
}有一说一现在写已经很熟了，进步肉眼可见
