本文主要是介绍代码随想录算法训练营第四十三天|1049.最后一块石头的重量II、494.目标和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1049.最后一块石头的重量II
public class Solution {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 [target+1];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-dp[target]-dp[target];}
}明确是一道动态规划题目，也是背包问题，每个数只能使用一次所以是01背包问题，稍加改造可得出状态转移方程Dp[j]=Math.Max(Dp[j],Dp[j-stones[i]]+stones[j])内层循环依旧是倒序处理。要想使得最后的石头重量最小，那就要将数组分成两堆，并且两堆总和差值越小越好，所以将Target设定大小为数组总和Sum的一半，最终返回结果即可。
494.目标和
public class Solution {public int FindTargetSumWays(int[] nums, int target) {int sum=0;int x=0;for(int i=0;i<nums.Length;i++){sum+=nums[i];}x=(sum+target)/2;int []dp=new int[10001];dp[0]=1;if((target+sum)%2==1)return 0;if((Math.Abs(target)>sum))return 0;for(int i=0;i<nums.Length;i++){for(int j=x;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[x];}
}这道题也是01背包问题，不过需要找出关系式子，Left+Right=Sum，Left-Right=Target，Left=(Sum+Target)/2，根据推到，初始化Dp[0]=1，只要搞到Nums[i]，凑成Dp[j]就有Dp[j - nums[i]] 种方法，所以状态转移方程为Dp[j]+=Dp[j-nums[i]]，还需要进行剪枝处理，如果Target比Sum大则直接返回，如果Target+Sum是奇数也不行，最终返回Dp[x]，X则是Left部分。
这篇关于代码随想录算法训练营第四十三天|1049.最后一块石头的重量II、494.目标和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
