回溯算法练习
回溯本质
回溯算法本质上是一种递归算法
一般用以解决下面的问题：
- 组合问题：从n个数里按照某个规则找出k个数；
- 切割问题：一个字符串按照一定的方法有几种切割方法；
- 子集问题：n个数里有多少符合条件的子集；
- 排列问题：n个数按照某种排列规则，有几种排列方法；
- 棋盘问题：n皇后等等；
解决过程
回溯的问题都能使用树形结构来解决，就是在树形结构中进行递归查找，即：集合的大小构成了树的宽度，递归的深度就是树的深度。
递归一定是要有终止条件，所以回溯问题构成的树，一定是一个有限深度的树。
解决模版
回溯问题的解决模版：(回溯三部曲）
- 确定回溯函数的返回值及参数；
- 回溯函数的终止条件；
- 回溯搜索的遍历过程；
1 | void backtracking(参数) { |
力扣实战
烹饪料理
欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢 复状态。
勇者背包内共有编号为 0 ~ 4 的五种食材，其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第 i 种料理需要第 j 种食材的数量，而 attribute[i] = [x,y] 表示第 i 道料理的美味度 x 和饱腹感 y。
在饱腹感不小于 limit 的情况下，请返回勇者可获得的最大美味度。如果无法满足饱腹感要求，则返回 -1。
注意：
每种料理只能制作一次。
示例 1：
输入：materials = [3,2,4,1,2]
cookbooks = [[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]
attribute = [[3,2],[2,4],[7,6]]
limit = 5
输出：7
解释：
食材数量可以满足以下两种方案：
方案一：制作料理 0 和料理 1，可获得饱腹感 2+4、美味度 3+2
方案二：仅制作料理 2， 可饱腹感为 6、美味度为 7
因此在满足饱腹感的要求下，可获得最高美味度 7
题目有点长，虽然题目整体难度不大，但还是有些注意点，我犯错了调试半天才发现。
结合前面的三部曲，
- 确定回溯函数的返回值及参数；
- 回溯函数的终止条件；
- 回溯搜索的遍历过程；
很快啊，我们就能确定返回值是一个 bestYummy(最大美味度 ，int数值)，随着递归深入，不断更新这个 值。
ok， 参数的话我们把题目里的条件都用上，多传递是没啥问题的，后面再优化嘛。
除了函数里已经给的 参数，我们需要传递 yummy(累计美味度, int类型) , 当前料理的id
ok 三部曲 第一部 完成
遇到id 为 n(总料理数，cookbooks.length) 结束循环， limit被用完更新最大值
ok 三部曲 第二部 完成
遍历过程比较重要，想象一下我们的树形结构，每层的决策都是一个二分，就是做或不做，to do or not to do 这个料理，ok， 我们就用两行递归代码搞定。
第一行递归是 not to do，为啥不是 to do，好问题～
第二行是to do，搞定这个to do前 需要去把相关的值做个更新，用于递归参数传递。
ok 至此 三部曲 第三部 完成
需要注意的点是，(敲黑板)
-
第二部曲 中， 结束循环 和 更新最大值的代码先后顺序！ 先更新再结束循环，否则最后一个料理如果是最优解的话就会错过～。～
-
第三部曲 中 递归传递的值发生更新的有 materials， yummy， id， limit， 需要注意的是materials的更新，它是一个数组，需要拷贝一份做修改，将修改的拷贝传入参数
