动态规划之-目标和(target sum)
- 前言
目标和的问题被划分在动态规划的体型范畴内，但是拿到题目的第一直觉是，这是一个典型的回溯题目，对于数组中的每个元素，我们可以选择添加+或添加-，值得一提的是，遍历过程中对于每个元素只有两个选择，要么赋值+号，要么赋值-号，不允许跳过任何元素进行操作。
如果要借助动态规划实现，则需要转换思维，转换为0-1背包问题，假定我们把正整数数组分为两个集合，一组集合里的元素前面冠以-号，一组集合前面冠以符号；假定冠以符号的所有元素的和为neg, 问题可以转化为，给定目标和定义为target
t
a
r
g
e
t
=
(
s
u
m
−
n
e
g
)
−
n
e
g
;
target=(sum-neg)-neg;
target=(sum−neg)−neg;
再进一步简化上面算式，最终可以得到求解neg的表达式，
n
e
g
=
(
s
u
m
−
t
a
r
g
e
t
)
/
2
neg=(sum-target)/2
neg=(sum−target)/2
接下来问题就可以抽象为0-1背包问题，从n个元素中选择某些元素，使其和等于neg。
具体问题描述，请参考Leetcod,494. 目标和 – 力扣（Leetcode）
- 解决方案
a.)回溯算法
对于回溯算法，其核心部分在于递归调用前后，对保留的赋值进行处理(power set问题 或 N皇后问题)，如果为二叉树，直接上两个递归函数即可解决问题。
之前的回溯算法的处理，都是在递归函数之前和递归函数之后，针对操作元素进行增删处理，本次递归和之前方案稍微不同，它直接是递归变量的值的改变，而递归变量本身的值被递归函数很好的保留下来，本身过程中并不发生任何改变。
这样的回溯的特点是，传递的递归变量值发生改变，而在递归函数里面的变量本身的值并不发生系统的改变，这是本次回溯算法的精华部分和值得学习地方。
b.) 动态规划算法
本问题可通过转换，形成0-1背包问题形式的动态规划算法，动态规划算法的状态转移方程可以参照0-1背包问题，很容易撰写出来。
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
,
i
f
j
<
n
u
m
s
[
i
]
dp[i][j]=dp[i-1][j],\ if\ \ j<nums[i]
dp[i][j]=dp[i−1][j], if j<nums[i]
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
+
d
p
[
i
−
1
]
[
j
−
n
u
m
s
[
i
−
1
]
]
,
i
f
j
<
n
u
m
s
[
i
]
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]],\ if\ \ j<nums[i]
dp[i][j]=dp[i−1][j]+dp[i−1][j−nums[i−1]], if j<nums[i]
动态规划的边界条件也非常清晰，如果不作任何选择，而且最终的总重为0的话，此方案就是最终结论之一，所以动态规划的基础dp[0][0]=1, 其实此条件其实等效于倒退到最后的值，而且值为0；那么之前的过程就是一个合理的值。
- 代码实现
代码实现的过程很常规，没有特别的地方。在回溯方法当中，如果对所有元素遍历/选择完成，此时如果总和等于目标值，那么就把数量加1.
/**
* @file target_sum.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-14
*
* @copyright Copyright (c) 2023
*
*/
#ifndef TARGET_SUM_C
#define TARGET_SUM_C
#include "target_sum.h"
int times=0;
void target_sum_backtrack(int *nums, int i, int nums_size, int target, int sum)
{
int j;
if(i==nums_size)
{
if(sum==target)
{
times = times + 1;
}
}
else
{
//i start from 0 index, it is better to understand this situation
target_sum_backtrack(nums,i+1,nums_size,target,sum+nums[i]);
target_sum_backtrack(nums, i + 1, nums_size, target, sum-nums[i]);
}
}
#endif
对于动态规划，相对而言稍微复杂，主要在于neg的计算方法
/**
* @file target_sum.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-14
*
* @copyright Copyright (c) 2023
*
*/
#ifndef TARGET_SUM_C
#define TARGET_SUM_C
#include "target_sum.h"
int target_sum(int *nums, int nums_size, int target)
{
int sum = 0;
for (int i = 0; i < nums_size; i++)
{
sum += nums[i];
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0)
{
return 0;
}
int n = nums_size, neg = diff / 2;
int dp[n + 1][neg + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
int num = nums[i - 1];
for (int j = 0; j <= neg; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= num)
{
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
#endif
- 总结
通过本示例学习，对回溯的方法和技巧有了更多的了解，同时对于动态规划的问题转换也有了直观的理解。对于回溯和动态规划，还需要继续练习，不断坚强巩固。
参考资料