asp.net mvc网站发布教程,网站建设微商城多少钱,系统优化软件哪个好,营销渠道和营销网络的建设进出栈的组合数
王道数据结构书里说栈进出组合数的时候#xff0c;让背公式把这个推导跳过去了#xff0c;我去网上看分析贴又翻到用深搜递归代码来解释问题的情况#xff0c;代码如下:
includeiostream
using namespace std;
int dfs(int i,int j){if(i0)return …进出栈的组合数
王道数据结构书里说栈进出组合数的时候让背公式把这个推导跳过去了我去网上看分析贴又翻到用深搜递归代码来解释问题的情况代码如下:
includeiostream
using namespace std;
int dfs(int i,int j){if(i0)return 1;//没有数要进栈,方案数为1int sum0;if(j0)sumdfs(i,j-1);//将一个数出栈sumdfs(i-1,j1);//将一个数进栈return sum;
}
int main(){int n;cinn;coutdfs(n,0);return 0;
}
看到这个代码不知道有多少人像我一样久久困惑于递归玄学原帖的解析如下 我们可以考虑用递归来枚举每一种状态对于每种状态它可以衍生出两种状态一:将一个数进栈二:将栈顶出栈 所以我们就可以给d f s dfsdfs函数设置两个参数一个是还没有进入栈的有多少个元素和栈内现在有多少个元素 所以可以定义d f s ( i , j ) dfs(i,j)dfs(i,j)的意思是还有i个元素没有进入和j个数未出栈的总方案 这样写起来应该会写吧主函数内调用的就是d f s ( n , 0 ) dfs(n,0)dfs(n,0)意思是n个数还没有进栈和0个数没有出栈的总方案 我过去写LeetCode或者蓝桥杯碰到这种其实都一只半解 为什么进一个数或者出一个数就调用递归还把返回值加到方案数最终就能得到方案数
终于这次停止空想开始手推这个过程 假设有初使空栈10个数需要进栈 每一步可以选择出栈或者进栈这其实很像一颗决策二叉树。 推得过程中逐渐发现
代码中sumdfs的位置其实就是二叉树每次长出新的分叉的位置每个dfs调用何时结束呢,也就是sum1什么时候发生那就是走到最后下面再也没有新的分叉的时候这决定递归结束条件是i0,及没有新的元素需要入栈了。然而每个分叉都会诞生一个新的选择方案所以每次dfs决定要进还是要出都加进sum里得到叶子节点结束调用时得到返回值。而每次分叉都诞生一个新的选择方案初始状态分叉诞生两个选择以后每次分叉诞生一个新的选择所以分叉数1就得到选择方案的总数。而每个方案都有最后一步都会诞生一个叶子节点方案数等于叶子节点的数量并且分叉是什么非叶子节点
