加法原理
解决一件事情，有k类方法，第i类方法有a[i]种选择。那么总方案数=a[1]+a[2]+....+a[k]
乘法原理
解决一件事情，有k个步骤，第i个步骤有a[i]种选择。那么总方案数=a[1] * a[2]....* a[k]
排列组合
排列：
将n个元素选取k个出来构成一个排列，总方案数$A_{n}^{k} $= \(\frac{n!}{(n-k)!}\)
组合：
将n个元素选取k个出来构成一个集合总方案数$C_{n}^{k} $= \(\frac{A_{n}^{k}}{k!}\)= \(\frac{n!}{(n-k)!k!}\)
多重集的排列与组合数
多重集的排列是指有k种元素，第i种元素的个数为a[i],总元素个数为n,其全排列的方案数为：
\[\frac{n!}{a1!a2!...ak!} \]多重集的组合数1：
设有k种元素，第i种元素的个数为a[i],取共计r个元素构成集合且r<=a[i]，其组合数：
证明：
考虑隔板法，因为每种元素都可以不选，考虑先给每种元素都选一个，那么也就是选r+k个，隔板法r+k-1个空隙，放k-1个隔板，那么每份隔出的数量-1对应选择该种元素的个数。因为r<=a[i]，所以无论隔出的情况如何都不存在出现一种元素选取个数大于其总个数的情况
组合数的常用性质
性质1：
\[C_{0}^{n}+C_{1}^{n}+....+C_{n}^{n}=2^n \]性质2：
\[C_{m}^{n}=C_{n-m}^{n} \]性质3：
\[C_{m}^{n}=C_{m-1}^{n-1}+C_{m}^{n-1} \]从动态规划的想法出发很好理解：
\(C_{m-1}^{n-1}\)其实就是第n个数选了，而\(C_{m}^{n-1}\)则是没选
写代码的话初始状态设\(dp[0][0]=1\)