算法刷题 | DP 45.4（目标与一零问题及背包问题例题回顾）

文章结构概览

• 12.目标和
  • • 12.1题目
    • 12.2解法：动态规划
    • • 12.2.1动态规划思路
      • 12.2.2代码实现

  • 13.一和零

  • • 13.1题目
    • 13.2解法：动态规划
    • • 13.2.1动态规划思路
      • 13.2.2代码实现

  • 14.0-1背包例题小结

12.目标与性能优化

12.题目设计与优化

给定一个由非负整数构成的数组 nums 以及一个整数 target 。

在数组中每个整数的前面添加 '+' 或 '-' 符号，随后将所有整数连接起来，即可形成一个 表达式 ：

• 例如，当 nums = [2, 1] 时，可以在 2 前面添加 '+' ，在 1 前面添加 '-' ，然后将这些符号与数字连接起来，得到表达式 "+2-1" 。

请计算通过上述方式能够构造出的所有 表达式 中，其运算结果等于 target 的不同 表达式 的数量。