某餐厅提供羊肉串，小王怕浪费每次最多只拿 3 串。已知他正好吃了 10 串， 那么他共有多少种不同的拿法？
答案：274 种。
思路（把问题转化为“1、2、3 串的有序分拆”） 每次最多拿 3 串，且为了吃满 10 串，每次至少拿 1 串。于是问题等价于：把 10 拆成若干个由 1、2、3 组成的有序和，顺序不同算不同。
设 表示吃满 串的拿法数，则有递推：
初值 （不拿也算一种空方案），，。
逐步计算：
&f(3)=4,\; f(4)=7,\; f(5)=13,\; f(6)=24,\\ &f(7)=44,\; f(8)=81,\; f(9)=149,\; f(10)=274. \end{aligned}$$ 因此共有 $\boxed{274}$ 种不同的拿法。 > 备选检验思路：设分别拿了 $a$ 次 1 串、$b$ 次 2 串、$c$ 次 3 串，则 $a+2b+3c=10$。对每组 $(a,b,c)$ 的排列数为 $\dfrac{(a+b+c)!}{a!\,b!\,c!}$，将所有满足方程的 $(a,b,c)$ 的该值求和，结果同为 274。 --- 某餐厅提供羊肉串，小王不怕浪费每次可以拿任意多串。已知他正好吃了 10 串，那么他共有多少种不同的拿法 --- ### 解法一 **答案：$\boxed{512}$ 种。** **思路（把问题转化为“正整数的有序分拆”）** 每次拿的串数为正整数，总数为 $10$。不同“拿法”即把 $10$ 拆成若干个正整数的**有序**和（顺序不同算不同），这就是“组合数（composition）”。 把 10 串排成一行，考虑它们之间的 9 个空隙，每个空隙要么“切开”（表示分一次拿），要么“不切”（并入同一次拿）。每个空隙两种选择、相互独立，因此： $$\#\text{拿法}=2^{9}=512.$$ > 一般地，正好吃 $n$ 串且每次可拿任意多（至少 1）串的拿法数为 $2^{n-1}$。 ### 解法二 **递推/动态规划**解法（每次可拿任意多串但至少 1 串，总数为 10）： **定义** 令 $f(n)$ 为吃满 $n$ 串的不同拿法数。 **状态转移** 第一次拿 $x$ 串（$1\le x\le n$），剩下的是规模为 $n-x$ 的同类子问题： $$f(n)=\sum_{x=1}^{n} f(n-x)=f(n-1)+f(n-2)+\cdots+f(0),$$ 其中取空和视作 1 种方案，故 **初值** $f(0)=1$。 由上式立刻得到一个更简洁的一阶递推： 因为 $$f(n-1)=f(n-2)+\cdots+f(0)$$ 两式相减得 $$f(n)=2\,f(n-1),\quad n\ge 1$$ 且 $f(1)=1$（只拿一次 1 串）。 **结论** $$f(n)=2^{\,n-1}\ \Rightarrow\ f(10)=2^{9}=512$$ > 说明：该问题等价于把 10 分解为正整数的**有序**和（composition）；在 9 个间隙处各自“切/不切”，共有 $2^{9}$ 种。上述递推正是这一计数的递推表达。 --- 某乡村公路的一侧共有 10 盏路灯，为了道路安全，连续的两盏不能同时熄灭，问一共 有多少种可能的亮灯方式？ --- **答案：$\boxed{144}$ 种。** **递推/DP 思路** 设 $f(n)$ 为 $n$ 盏路灯的可行亮灯方式数（相邻两盏不能同时熄灭）。 * 若第 1 盏亮（1），后面 $n-1$ 盏任意合法：共有 $f(n-1)$ 种。 * 若第 1 盏灭（0），则第 2 盏必须亮（1），后面 $n-2$ 盏任意合法：共有 $f(n-2)$ 种。 故有斐波那契型递推： $$f(n)=f(n-1)+f(n-2),$$ 初值： $$f(1)=2\ \big(\{1,0\}\big),\qquad f(2)=3\ \big(\{11,10,01\}\big).$$ 自底向上计算： $$\begin{aligned} &f(3)=5,\ f(4)=8,\ f(5)=13,\ f(6)=21,\\ &f(7)=34,\ f(8)=55,\ f(9)=89,\ f(10)=144. \end{aligned}$$ 因此共有 $\boxed{144}$ 种亮灯方式。（一般地 $f(n)=F_{n+2}$，其中 $F_k$ 为斐波那契数、$F_1=1,F_2=1$。） --- 某乡村公路的一侧共有 10 盏路灯，其中有7盏灯是亮的，为了道路安全，连续的两盏不能同时熄灭，问一共有多少种可能的亮灯方式？ --- **答案：$\boxed{56}$ 种。** ### 组合计数（插空法，最简洁） 先把 7 盏亮灯（记作 1）排好： $$1\ \_\ 1\ \_\ 1\ \_\ 1\ \_\ 1\ \_\ 1\ \_\ 1$$ 共有 $7+1=8$ 个“空位”（含两端）。为了“禁止相邻两盏都灭”，3 个灭灯（记作 0）必须分散到不同空位里。 因此方案数为从 8 个空位中选 3 个：$\binom{8}{3}=56$。 ### 递推/DP 思路 设 $g(n,m)$ 为长度为 $n$ 的灯串中恰有 $m$ 盏熄灭、且无相邻熄灭的方案数。 首位讨论得递推： $$g(n,m)=g(n-1,m)\;+\;g(n-2,m-1),$$ * 首位为亮：后面是 $g(n-1,m)$； * 首位为灭：次位必须亮，后面是 $g(n-2,m-1)$。 边界：$g(0,0)=1$，$g(n,0)=1$（全亮），其余不合法处为 0。 自底向上可得 $g(10,3)=56$。 > 一般结论：长度 $n$ 中恰有 $k$ 个 0 且无相邻 0 的方案数为 $\binom{n-k+1}{k}$；或等价地“恰有 $s$ 个 1、$k$ 个 0”时为 $\binom{s+1}{k}$。本题 $s=7,k=3\Rightarrow\binom{8}{3}=56$。 --- 某乡村公路的一侧计划种 10 棵树苗，每棵树苗可以在桃树、柳树和梨树中选择，要求连续三棵树不能完全相同，共有多少种不同的种法？ --- **答案：$\boxed{27408}$ 种。** ### 递推 / DP 设 $f(n)$ 为长度为 $n$ 的种树序列（每棵从“桃/柳/梨”三选一）且**不存在连续三棵相同**的方案数。 按最后两棵是否相同分类： * **末两棵不同**：先取任意一个合法的长度 $n-1$ 序列（$f(n-1)$ 种），最后一棵可在与倒数第二棵不同的 2 种树中选，得 $2f(n-1)$ 种。 * **末两棵相同**：看作先取一个合法的长度 $n-2$ 序列（$f(n-2)$ 种），第 $n-1$ 棵需与第 $n-2$ 棵不同（2 选 1），第 $n$ 棵与第 $n-1$ 棵相同（1 种），共 $2f(n-2)$ 种。 于是得到递推（对 $n\ge3$）： $$f(n)=2f(n-1)+2f(n-2),$$ 初值：$f(1)=3$（任取其一），$f(2)=3^2=9$。 自底向上： $$\begin{aligned} &f(3)=2(9)+2(3)=24,\\ &f(4)=2(24)+2(9)=66,\\ &f(5)=180,\ f(6)=492,\ f(7)=1344,\\ &f(8)=3672,\ f(9)=10032,\ f(10)=27408. \end{aligned}$$ **一般化**：若每棵树可从 $k$ 种中选，且禁止出现三连相同，则 $$f_k(n)=(k-1)\bigl(f_k(n-1)+f_k(n-2)\bigr),\quad f_k(1)=k,\ f_k(2)=k^2$$ 本题 $k=3$，即 $f(n)=2\bigl(f(n-1)+f(n-2)\bigr)$。 --- 你是一个侠盗，计划偷窃沿街的坏人劫富济贫。影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。沿街房屋内 10 户人家的金额分别为【2,7,9,8,4,4,6,5,9,7】（单位：万元）计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 ---- ### 状态与含义 令 $v[i]$ 表示第 $i$ 户金额（1 基），$dp[i]$ 表示**前 $i$ 户**在不触发警报（相邻不可同晚行窃）的前提下，能偷到的**最高金额**。 ### 转移的来源：最后一户“偷 or 不偷”的二选一 考虑最优解在第 $i$ 户上的选择： * **不偷第 $i$ 户**：那前 $i$ 户的最优值就是前 $i-1$ 户的最优值，即 $dp[i-1]$。 * **偷第 $i$ 户**：由于与第 $i-1$ 户相邻，**第 $i-1$ 户必须不偷**。于是前 $i$ 户的收益是“第 $i$ 户金额 + 前 $i-2$ 户最优值”，即 $v[i]+dp[i-2]$。 在这两种互斥选择中取最大，得到**状态转移方程**： $$dp[i]=\max\big(dp[i-1],\ dp[i-2]+v[i]\big).$$ ### 边界条件 $$dp[0]=0,\qquad dp[1]=\max(0,v[1])=v[1]\ (\text{本题金额均非负})$$ > 直观理解：第 $i$ 户要么被纳入最优方案（那就不能要第 $i-1$ 户），要么不纳入（那就承接前 $i-1$ 户的最优），这就是“最优子结构”，因此可用动态规划。 计算步骤略 **结论**：最高金额 $dp[10]=31$ 万元。 （若要恢复具体偷哪几户，可从尾到头比较 $dp[i]$ 与 $dp[i-1]$；若 $dp[i]=dp[i-1]$ 则第 $i$ 户不偷，否则偷第 $i$ 户并令 $i\leftarrow i-2$ 继续回溯。） ---