【算法训练记录——Day42】

1.leetcode_1049最后一块石头的重量II

思路：石头只能用一次。。。怎么才能让碰撞后重量最小呢，还要转换成动态规划，难以理解。。
看题解：碰撞后重量最小，即将石头分为两组尽可能重量相等。
我理解就是背包容量等于石头总重量的一半，尽可能让背包装满吧，即背包最大容纳重量。

	int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i : stones)
            sum += i;

        int target = sum / 2;

        vector<int> dp(target + 1, 0);

        for(int i = 0; i < stones.size(); i++) {
            for(int j = target; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }

        return sum - 2 * dp[target];
    }

哦吼，蒙对了

2.leetcode_494目标和

思路：暴力回溯

	int backtracking(const vector<int>& nums, const int& target, int num, int sum) {
        if(num == nums.size() - 1 && sum == target) {
            return 1;
        }
        if(num == nums.size() - 1) {
            return 0;
        }
        
        // cout << nums[num] << " +  " << " " ;
        int res = backtracking(nums, target, num + 1, sum + nums[num + 1]);
        // cout << "res : " << res  << endl;
        // cout << num << " -  " << nums[num] << " ";
        res += backtracking(nums, target, num + 1, sum - nums[num+1]);
        // cout << "res : " << res  << endl;

        return res;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        return backtracking(nums, target, 0, nums[0]) + backtracking(nums, target, 0, -nums[0]);
    }

代码有点冗余，，修改一下：

	int backtracking(const vector<int>& nums, const int& target, int num, int sum) {
        if(num == nums.size() && sum == target) {
            return 1;
        }
        if(num == nums.size()) {
            return 0;
        }
        
        // cout << nums[num] << " +  " << " " ;
        int res = backtracking(nums, target, num + 1, sum + nums[num]);
        // cout << "res : " << res  << endl;
        // cout << num << " -  " << nums[num] << " ";
        res += backtracking(nums, target, num + 1, sum - nums[num]);
        // cout << "res : " << res  << endl;

        return res;
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        return backtracking(nums, target, 0, 0);
    }

思路二：动态规划，很抱歉，暂时想不到怎么规划。。。看题解吧
别急，好像有点思路，背包，容量，物品个数。那么是否可以看成，target为背包容量，物品价值可以有+ - nums[i]，最大价值==背包容量的数目？？？瞎猜确实没用，看题解

好好好，再试试
难的是dp的递推公式怎么得出：

1. 填满j（包括j）这么大容积的包，有dp[j]种方法

2. 有哪些来源可以推出dp[j]呢？
   只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

   例如：dp[j]，j 为5，

   已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
   已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
   已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
   已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
   已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包
   那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
   dp[j] = dp[j] + dp[j-nums[i]];

	int findTargetSumWays(vector<int>& nums, int target) {
        // return backtracking(nums, target, 0, 0);
        int sum = 0;
        for(int i : nums)
            sum += i;
        if(abs(target) > sum) return 0;
        target = sum + target;
        if(target % 2 == 1)
            return 0;
        target >>= 1;

        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for(int i = 0; i < nums.size(); i++)
            for(int j = target; j >= nums[i]; j--) {
                dp[j] += dp[j-nums[i]];
            }

        return dp[target];
    }

3.leetcode_474一和零