P1036 [NOIP2002 普及组] 选数 深搜题解

题目描述

给定一个长度为 $n$ 的序列 $a$，选出其中的若干个数，使得它们的和恰好为 $k$，求有多少种选法。

解题思路

这道题也可以使用深度优先搜索（DFS）来解决。我们可以枚举每个数 $a_i$ 是否被选中，然后递归地搜索下一个数 $a_{i+1}$。如果已经选出的数的和为 $k$，则说明找到了一种选法。

具体地，我们可以定义一个函数 $dfs(i, sum)$，其中 $i$ 表示当前考虑到的数的下标，$sum$ 表示已经选出的数的和。函数的返回值表示在后面的数中选出若干个数恰好为 $k-sum$ 的选法数目。

如果 $sum=k$，则说明找到了一种选法，返回 $1$。

如果 $sum>k$ 或者 $i>n$，则说明选出的数的和已经超过了 $k$，或者已经考虑完了所有的数，因此返回 $0$。

否则，对于第 $i$ 个数 $a_i$，有两种情况：选或者不选。如果选第 $i$ 个数，则 $sum$ 加上 $a_i$，继续递归搜索下一个数 $a_{i+1}$；如果不选第 $i$ 个数，则直接递归搜索下一个数 $a_{i+1}$。最终的答案为选或者不选第 $1$ 个数的选法数目之和。

代码实现

相关问题

P1036 [NOIP2002 普及组] 选数 题解

题目描述

给定一个长度为 $n$ 的序列 $a$，选出其中的若干个数，使得它们的和恰好为 $k$，求有多少种选法。

解题思路

这道题可以使用动态规划来解决。设 $dp[i][j]$ 表示前 $i$ 个数中选出若干个数恰好为 $j$ 的选法数目，则有状态转移方程：

$dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]$

其中 $dp[i-1][j]$ 表示不选第 $i$ 个数的选法数目，$dp[i-1][j-a[i]]$ 表示选第 $i$ 个数的选法数目，因为选第 $i$ 个数后，剩下的 $i-1$ 个数中选出若干个数恰好为 $j-a[i]$。

最终答案为 $dp[n][k]$。

代码实现

P1036 [NOIP2002 普及组] 选数

这是一道IT类问题，题目描述如下：
给定一个长度为n的序列a，选出其中的若干个数，使得它们的和恰好为k，求有多少种选法。

这道题可以使用动态规划来解决。设dp[i][j]表示前i个数中选出若干个数恰好为j的选法数目，则有状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]

其中dp[i-1][j]表示不选第i个数的选法数目，dp[i-1][j-a[i]]表示选第i个数的选法数目，因为选第i个数后，剩下的i-1个数中选出若干个数恰好为j-a[i]。

最终答案为dp[n][k]。