Leetcode494. 目标和(HOT100)

链接

代码一：
纯递归：
 

// 递归
class Solution {
public:
    int cnt=0;
    void dfs(vector<int> &a,int u,int target,int sum)
    {
        if(u==a.size())
        {
            if(sum==target) cnt++;//当 u
            // 等于数组的大小时，表示已经处理了所有的元素，此时检查 sum 是否等于target 
            return;
        }
        dfs(a,u+1,target,sum+a[u]);
        dfs(a,u+1,target,sum-a[u]);
    }
    int findTargetSumWays(vector<int>& a, int target) {
        dfs(a,0,target,0);//递归的数组，递归到了哪个下标，递归的和，当前和
        return cnt;
    }
};
// //
// 在这段代码中，时间复杂度是O(2^n),原因是因为我们对每个元素都有两个选择：要么加上这个元素，要么减去这个元素。这里的n是数组的长度。

代码二：
动态规划：

//dp
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& a, int target) {
//         int n = a.size(), Offset = 1000;//设置一个偏移量，用于将负数索引转换为非负索引。由于 target 和数组元素的范围是 [-1000, 1000]，我们可以将其映射到 [0, 2000] 的范围。
//         if (target < -1000 || target > 1000)
//             return 0;
//         vector<vector<int>> f(n + 1, vector<int>(2001));// f[i][j] 表示使用前 i 个元素，得到和为 j 的方式有多少种。
//         f[0][0 + Offset] = 1;//初始化条件，表示使用 0 个元素得到和为 0 的方式有 1 种（什么都不做）。
//         for (int i = 1; i <= n; i++) {//遍历数组所有元素
//             for (int j = -1000; j <= 1000; j++) {//每遍历到某个元素，都查看加上它或者减去它，得到的结果还在不在范围中，如果在，就存起来
//                 if (j - a[i - 1] >= -1000)//如果当前和减去当前元素仍在有效范围内，更新状态
//                     f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset];
//                 if (j + a[i - 1] <= 1000)//如果当前和加上当前元素仍在有效范围内，同样更新状态
//                     f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset];
//             }
//         }
//         return f[n][Offset + target];//返回使用 n 个元素得到目标和 target 的方式有多少种。
//     }
// };