一、前言
? ? ? ? 今天很例外哈，做了两题，是因为我觉得第一题题型前两天遇见过，所以有些熟悉，很快就写出来了，然后就想着多写一题，结果第二题还是挺常规的，那今天就这两题吧，开始。
二、题目描述（1035）
????????
?三、题目分析
?????????这道题乍一看挺吓人的，因为要考虑到图形化的线段相交问题，但是其实却不难，因为只要将dp的前一种情况，最基础的情况考虑清楚了，那么dp后面的公式就很容易得出，那么也就不会错了。
? ? ? ? 这个题目很容易看出来，用一个二维数组dp[i][j]储存，它的含义是，nums1的前i个数和nums2的前j个数中最多的不相交线段数。为了防止边界的判断问题，我们将dp的长度设置为
int [][]dp=new int [nums1.length][nums2.length];? ? ? ? 于是得出他的边界条件为，dp[0][0]=dp[0][1]=dp[1][0]=0;之后得出状态转移方程，dp[i][j]等于什么呢？如果nums1的第i个和nums2的第j个相等，那么很明显，dp[i][j]=dp[i-1][j-1]+1
如果不相等，那么dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])，最后我们只需要返回nums1的前nums1.length个数和nums2的前nums2.length个数的不相交线段数，即dp[nums1.length][nums2.length]即可。
四、代码
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][]dp=new int [nums1.length+1][nums2.length+1];
int len1=nums1.length;
int len2=nums2.length;
dp[0][0]=0;
dp[0][1]=0;
dp[1][0]=0;
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(nums1[i-1]==nums2[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];
}五、代码优化
? ? ? ? 我们发现，二维数组遍历需要花费大量时间，而且有些时间和空间的消耗是不必要的，那我们可以考虑用一维数组代替二维数组，通过定义的变量来代替原本另外一维数组的操作。
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1=nums1.length;//设置nums1的长度
int len2=nums2.length;//设置nums2的长度
int[]dp=new int [len2+1];//dp数组代表nums2
for(int i=1;i<=len1;i++)
{
int last=dp[0];//储存之前的dp
for(int j=1;j<=len2;j++)
{
int tmp=dp[j];//储存当前的dp
if(nums1[i-1]==nums2[j-1])
dp[j]=last+1;//不用dp[j-1]是因为它被覆盖了
else
dp[j]=Math.max(dp[j-1],dp[j]);
last=tmp;//重新赋值
}
}
return dp[len2];
}
?
六、题目描述（1049）
七、题目分析
?????????这题还是属于一个背包问题，可以其实就是将这个大数组转化为两个小数组，最优值就是当两个数组的差最小产生。那么这就和原来写过的一题很相似啦，我们先定义一个目标值target为整个大数组和的一半（如果是奇数就取sum/2）。那么dp[i][j]的含义就是stones前i个数中加起来不超过j的数的值，最后我们返回的就是dp[stones.length][target]，表示前length个数中，最接近target的值，那么用sum-2*dp[stones.length][target]做返回值就可以得出答案啦（其中sum-dp[stones.length][target]是另一边的值）。
? ? ? ? 那么它的状态转移方程怎么列呢？还是跟之前一样的很简单的套路，首先判断j和stones[i-1]的大小关系，如果j大，呢么这个第i个数可放可不放，取最大值即可，如果j小，那么stones[i-1]肯定不能放，因为一放的话，就超了。所以状态转移方程为：
if(j>=stones[i-1])
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
else
dp[i][j]=dp[i-1][j];八、代码
????????
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i=0;i<stones.length;i++)
{
sum+=stones[i];
}
int target=sum/2;
int dp[][]=new int [stones.length+1][target+1];
for(int i=1;i<=stones.length;i++)
{
for(int j=1;j<=target;j++)
{
if(j>=stones[i-1])
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
else
dp[i][j]=dp[i-1][j];
}
}
return (sum - dp[stones.length][target]) - dp[stones.length][target];
}九、感言
? ? ? ? 动态规划也写了有几天了，发现确实或多或少都是那些套路，只看个人怎么给它转化成容易理解的形式罢了。这几天下来，简单的题目都可以轻松搞定，中等的题目也能大差不差的写完，但是我还没有尝试较困难的题目，明天开始可以试试。动态规划的题目我看了一下有三十多题，我自然没时间全都写一遍，所以我决定再写两天的难题目就换到下个模块了，这个动态规划的版块如果以后有机会还会再写的。
? ? ? ? 最后，flag不倒，每日一题！！！