揭秘Adobe Flash Player的秘密武器：代码解析与优化技巧全分享

Day 43 动态规划 part05（01背包问题part02）

今日任务

• 1049. 最后一块石头的重量 II
• 494. 目标和
• 474.一和零

代码实现

1049. 最后一块石头的重量 II

publicintlastStoneWeightII(int[] stones){int sum =Arrays.stream(stones).sum();//表示大小为i的背包中最多能装dp[i]的东西int[] dp =newint[sum/2+1];for(int i =0; i < stones.length; i++){for(int j = sum/2; j >= stones[i]; j--){
                dp[j]=Math.max(dp[j], dp[j - stones[i]]+ stones[i]);}}return sum - dp[dp.length -1]- dp[dp.length -1];}

494. 目标和

publicintfindTargetSumWays(int[] nums,int target){int sum =Arrays.stream(nums).sum();if((target + sum)%2==1)return0;if(target > sum)return0;int targetSum =(target + sum)/2;int[] dp =newint[targetSum +1];for(int i =0; i < nums.length; i++){for(int j = targetSum; i >= nums[i]; j--){
                dp[j]+=dp[j - nums[i]];}}return nums[targetSum];}

474.一和零

publicintfindMaxForm(String[] strs,int m,int n){int[][] dp =newint[m +1][n +1];for(String str : strs){int zeroCount =0;int oneCount =0;for(char c : str.toCharArray()){if(c =='0'){
                    zeroCount++;}elseif(c =='1'){
                    oneCount++;}}for(int j = m; j >= zeroCount; j--){for(int k = n; k >= oneCount; k--){
                    dp[j][k]=Math.max(dp[j][k], dp[j - zeroCount][k - oneCount]+1);}}}return dp[m][n];}

今日总结

1. 没什么可说的，太难了，基本上是凭着记忆在写，希望面试能碰到原题
2. 股票今天小亏，板块轮动太快，没什么像样的主线，亦或是这就是正常的节奏？早上强的下午就回落，下午就不一定拉哪一个，乱七八糟什么都可能涨，什么叫顺周期？