剑指offer专项突击版第34天

剑指 Offer II 100. 三角形中最小路径之和

经典线性dp

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for(int i = 1; i < n; i++) { //处理边界，以防stack overflow
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
        }

        for(int i = 2; i < n; i++) 
            for(int j = 1; j < i; j++)
                triangle[i][j] += min(triangle[i-1][j],triangle[i-1][j-1]); 

        int res = 0x3f3f3f3f;
        for(int i = 0; i < n; i++) res = min(res,triangle[n-1][i]);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

剑指 Offer II 101. 分割等和子集

1. 容易想到若 $nums$ 的总和为奇数，或最大数大于和的一半（$target$），一定为 $false$。
2. 若总和为偶数，接下来就是找是否有子序列的和为 $target$，这里就需要用到 $DP$ 方程 $f[i]|=f[i-num]$ ，其中 $f[i]$ 表示 $i$ 是否存在。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int total = 0, maxx = -0x3f3f3f3f;
        for(const int &num: nums) {
            total += num;
            maxx = max(maxx,num);
        }
        if(total % 2 || total/2 < maxx) return false;
        int target = total / 2;
        vector<int> f(target+1, 0);
        f[0] = true;
        for(int i = 0; i < n; i++) {
            int num = nums[i]; //将nums[i] 换成num速度快了一倍。。
            for(int j = target; j >= num; j--)
                f[j] |= f[j-num];
        }
            
        return f[target];            
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

剑指 Offer II 102. 加减的目标值

1. $neg$ 表示添加 $-$ 的整数之和，$sum$ 为 $nums$ 所有数之和，那么 $(sum-neg)-neg$ 则为添加 $+$ 的整数之和。
2. 那么可以推导出：$(sum-neg)-neg=sum-2\ast neg=target$。进而推导出：$neg=(sum-target)/2$。
3. 所以发现若 $nums$ 存在子序列之和为 $neg$ 那么就可以构造结果为 $target$ 的表达式。问题进而转化成：找出 $nums$ 的子序列之和为 $neg$ 的子序列总数。
4. 这个问题由 $DP$ 来解决，设 $f[i][j]$ 为 $nums$ 前 $i$ 个元素和为 $j$ 的子序列个数。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0, n = nums.size();
        for(int num: nums) total += num;
        int diff = total - target;
        if(diff < 0 || diff % 2) return 0; //若target大于total 或 diff为奇数则直接返回
        int neg = diff / 2;  //neg = (total - target) / 2
        vector<vector<int>> f(n+1, vector<int>(neg+1, 0));
        f[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            int num = nums[i-1];
            for(int j = 0; j <= neg; j++) {
                if(j < num) {
                    f[i][j] = f[i-1][j];
                } else {
                    f[i][j] = f[i-1][j] + f[i-1][j-num];
                }
            }
        }

        return f[n][neg];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

优化成一维空间

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = 0, n = nums.size();
        for(int num: nums) total += num;
        int diff = total - target;
        if(diff < 0 || diff % 2) return 0; 
        int neg = diff / 2;
        vector<int> f(neg+1, 0);
        f[0] = 1;
        for(int i = 1; i <= n; i++) {
            int num = nums[i-1];
            for(int j = neg; j >= num; j--) {
                f[j] += f[j-num];
            }
        }

        return f[neg];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20