23 | 深入理解：容斥原理与递推算法
胡光
你好，我是胡光，欢迎回来。
上两节呢，我们学习了两个具有单调性的数据结构：单调队列和单调栈。其中，单调队列是用来维护滑动窗口内的区间最值的单调结构，单调栈是用来维护最近大于或小于关系的单调结构。这两种单调结构的均摊时间复杂度都是 ，每个元素的操作次数最多是 2 次，足以看到这两种结构的高效。如果想彻底掌握这两种结构，我建议你在课下时间不断地练习。
从今天开始呢，我们将从数据结构，跳跃到算法的学习上。将要带你认识一类比较偏重于思维的算法，大类叫做递推算法，以及其中的一个重要的组成部分，动态规划类算法。
关于递推算法，在“语言基础篇”的第 05 讲《数组：一秒钟，定义 1000 个变量》中，我们其实就使用了递推算法的思想。如果你已经忘了的话，我建议你可以先回去看看，复习一下之前的内容，为今天的课程做好充足的准备。
今日任务
咱们今天这 10 分钟的任务呢，和钱有关系。众所周知，在不计算小于 1 元钱的面额的前提下，我国的纸币系统中，曾经拥有如下面值：1 元、2 元、5 元、10 元、20 元、50 元 和 100 元。假设，每一种面值的纸币，我们都有无限张，现在想用这些钱凑出 1000 元，请问你有多少种不同的方案？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了容斥原理与递推算法的相关概念和应用。首先介绍了容斥原理，指出在计数问题中，为了保证准确计数，需要注意避免重复和遗漏。容斥原理的基本思想是先不考虑重叠情况，计算所有对象的数目，然后排除重复计数的部分，以保证计算结果无遗漏且无重复。接着以兔子繁殖问题为例，阐述了递推算法的应用。递推算法通常分为三步：确定递推状态，推导递推公式，程序设计与编写。通过分析问题中的自变量和因变量，确定了具有明确含义的数学符号，如f(n)代表第n个月兔子的数量，作为状态定义。最后，介绍了递推问题的求解步骤，强调了递推算法的重要性和应用价值。整体而言，本文深入浅出地介绍了容斥原理和递推算法的概念及应用，对读者理解相关技术具有一定的指导意义。文章内容涵盖了递推问题的求解过程，强调了递推算法的重要性和应用价值，对读者理解相关技术具有一定的指导意义。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59
《人人都能学会的编程入门课》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(13)
- 最新
- 精选
徐洲更还有一个问题，把零钱兑换改成爬楼梯，每次是1,2,5,10 然后要爬到第100层 的走法 和零钱兑换的状态定义有什么不同呢作者回复: 有不同，爬楼梯的方案是在乎顺序的，凑钱币问题，是不在乎顺序的。爬楼梯，本质上，一维递推状态定义即可，由于在乎顺序，所以，只需要考虑最后一步走什么即可。
2020-03-104- 徐洲更这节课最大的收获就是 状态数组的定义，之前之前靠经验，现在学到了如何用因变量和自变量来定义
作者回复: perfect！
2020-03-104 
栾~龟虽寿！真的叹为观止，自变量，因变量，容斥原理，数学功底深厚，算法的底层是数学，展现的淋漓尽致。喵。作者回复: ^_^
2020-03-123
宋不肥关于递归的优化，其实可以考虑用数组构建一个散列表，将已经计算的值记录下来，当再次遇见时，先查询散列表中是否存在（O（1）），如果存在直接调用，从而避免重复计算.。作者回复: 对的，没错！
2020-03-142- 宋不肥其实关于狄利克雷卷积，不仅可以可以推导莫比乌斯反演这种离散情况，同时他也是大名鼎鼎得傅里叶变换得基础，在工科专业里面卷积常用于求一个系统得响应，初学时候总是不理解，其实是可以结合容斥与递推来理解得，一个系统当前得输出应该等于之前所有得输入在当前时刻得响应，也就是在保持容斥状态下求所有前项输入在当前是个得响应之和。同样傅里叶变换也是在容斥得要求下便利所有时间对所求频率得响应和，虽然是积分，但到了计算机里面也是加法了。初学时候要是考虑到每个时间点之间是容斥的，也会好理解的多。果然数学都是相通的。
作者回复: 赞，说的很透彻！
2020-03-141 - 徐洲更解答下问下递归慢，递归慢是因为递归树中有大量重复计算，f(6) 需要计算f(5)和f(4) , 而f(5)需要计算f(4) f(3), 计算机不会自动复用f(4)计算结果 而是要重复算
作者回复: 对的！所以，再结合：数组是展开的函数，函数是压缩的数组。你能想到什么？
2020-03-1021 
🤪HappyJoofibonacci的问题：int 的字节，算到第47个fibonacci的数的时候，就不够用了，可以用long，当然，long 只有8个字节，也就算到第92个，有兴趣的同学可以用前面学过的大数字表达法哈哈哈。 我的问题：为什么递归那么慢，用循环一下子就出结果了，应该也就是算了92次，递归算了几分钟还没有算出来，循环毫秒内就算好了。“它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作”，虽然我不知道堆栈是啥，但反正就调用了很多次函数，效率很低。好像可以用尾递归解决？（尾递归参考：https://www.zhihu.com/question/20761771，他写出了每一层的区别）作者回复: 循环快，是因为没有做多余运算，递归慢，是因为做了多余的运算。具体参考，@陈洲更 的留言。 关于递归程序的优化，其实是想让你们更深刻的理解：数组是展开的函数，函数是压缩的数组。这句话。
2020-03-101
佐西玛用递归算兔子的数量： int cal_rabbit_num(int n) { if(n == 1 || n == 2) { return 1; } return cal_rabbit_num(n - 1) + cal_rabbit_num(n - 2); } 用循环算兔子的数量： int cal_rabbit_num_loop(int n) { if(n == 1 || n == 2) { return 1; } int n1 = 1; int n2 = 1; int n3 = 0; for(int i = 0; i < n - 2; i++) { n3 = n1 + n2; n1 = n2; n2 = n3; } return n3; } 凑钱： int cal_coins(int i, int j) { if(j < 0) { return 0; } if(j == 0) { return 1; } if(i == 1 && j % val[1] == 0) { return 1; } return cal_coins(i - 1, j) + cal_coins(i, j - val[i]); } int main() { int n; scanf("%d", &n); printf("%d\n",cal_coins(3, n)); return 0; } 能不能公布一下答案，看看自己有没有算错。多谢船长！作者回复: 答案的话，在后面是有专门文章的，你可以往后看看。另外你的凑钱币代码中，i == 1 && j % val[1] 这里写错了，应该是 j % val[i] == 0。不过从代码能看出来，你是理解了思路的，加油！d(^_^o)
2020-06-04- 宋不肥//凑钱币 更改版 #include<stdio.h> int a[7] = {1,2,5,10,20,50,100}; int f_money(int i,int j){ if( i == 1 || j == 0 ) return 1; if(a[i-1] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-1]); if(a[i-2] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-2]); if(a[i-3] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-3]); if(a[i-4] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-4]); if(a[i-5] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-5]); if(a[i-6] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-6]); } int main(){ int v; v = f_money(7,1000); printf("%d",v); }
作者回复: 这回逻辑上还有那么点儿意思。d(^_^d)
2020-03-15 - 宋不肥作业打卡： //兔子繁殖 #include <stdio.h> // 递归 long f_recursive(int x){ if( x == 2 || x == 1) return 1; return f_recursive(x-1)+f_recursive(x-2); } //递推循环 long f_recursion(int x){ if( x == 2 || x == 1) return 1; long sum = 1 ,pre = 1,temp = 0; for(int i = 3;i <= x; ++i){ temp = sum; sum += pre; pre = temp; } return sum; } int main(){ long a = 0; a = f_recursive(20); printf("%ld\n",a); a = f_recursion(20); printf("%ld\n",a); } //凑钱币 #include<stdio.h> int a[7] = {1,2,5,10,20,50,100}; int f_money(int i,int j){ if( i == 1 || j == 1 ) return 1; if(a[i-1] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-1]); if(a[i-2] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-2]); if(a[i-3] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-3]); if(a[i-4] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-4]); if(a[i-5] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-5]); if(a[i-6] <= j ) return f_money(i-1,j) + f_money(i,j-a[i-6]); } int main(){ int v; v = f_money(7,1000); printf("%d",v); }
作者回复: 凑钱币问题的程序实现有问题，递归边界条件没有控制好，你试试 f_money(2, 2)，想想为什么程序错了。
2020-03-14
收起评论
