思路

1. 写的是搜索;
2. 判断条件:总和sum大于B(我写的是m)的时候,记录个数,也就是递归深度;通过记录历史最小个数ans和前缀和来判断要不要继续递归

问题

取最小值的写法一TLE改到写法二就AC了;

int dfs(int index, ll sum, int cnt)
{
	int ret = INT_MAX;
	if (index > 1) {
		if (sum < m && cnt <= ans) {
			for (int i = index - 1; i >= 1; i--) {
				if (sum + a[i] >= m ) { 
					ret = cnt + 1;
					ans = min(ans, cnt + 1);
					break;
				} else if ( cnt < ans &&  sum + summa[i] >= m) {
//					int temp = dfs(i, sum + a[i], cnt + 1);//写法一

//					if (temp != INT_MAX) {//写法二
//						ret = temp;
//						break;
//					}
				} else {
					break;
				}
			}
		}
	}
	return ret;
}

通过给函数加printf("%d %d %d\n",index,sum,cnt);可以观察到递归函数的下标一直在递减,然后代码中的index>1 是限制了递归深度的,我感觉没有问题;但是就是跑不出答案,不知道哪位大佬能指点一下?

代码

AC TLE