问题：给定一排n个硬币，其面值均为整数c1, c2, ..., cn, 这些整数并不一定两两不同。问如何选择硬币，使得在其原始位置互不相邻的条件下，所选硬币的总金额最大。
解决方案——递归法：
设对n个硬币，所选硬币最大总额为F(n)。对于F(n)，它可由以下计算方法得到，当已知F(n-2)，F(n-1)，则F(n)可以由F(n-2)与第n个硬币组成，即第n个硬币与它左边不相邻的第一个硬币的最大总值组合的组合；也可由F(n-1)组成即第n个硬币的左边相邻的硬币的最大总值组合。取哪个组合方法视乎哪种方法得到的F(n)比较大。例如，对硬币序列5,1,2,10,6,2，当n=3，即c3=2时，F(n)=max{F(n-2)+c3,F(n-1)}，其中第n个硬币与它左边不相邻的第一个硬币的最大总值组合的组合为{2,5}，第n个硬币的左边相邻的硬币的最大总值组合为{5}（注：F(n-1)=5是因为当n=2，不取1取5总面值大），得出F(3)=7。
递归需要初始值，所以这里F(1)=c1，由于需要配合F(2)，所以设定F(0)=0，使之不对F(2)产生影响：F(0)+c2。
除了计算出所选硬币的总金额的最大值，我们还想得出组成最大金额的选法，此时，我们需要用回溯法，从得到最大总金额的硬币开始回溯。如果F(n)=F(n-1)，这说明，最大总金额不包括第n个硬币，返回第n-1个硬币，继续回溯；如果F(n)=cn+F(n-2)，说明最大总金额包括第n个硬币，返回第n-2个硬币，继续回溯。该回溯直至n<=1停止。
示例：
下面对硬币序列5,1,2,10,6进行一次手动递归法演示。
首先建表1如下：
第一遍：F(2)=max{F(0)+c2,F(1)}=max{1,5}=5，所以有表2：
第二遍：F(3)=max{F(1)+c3,F(2)}=max{7,5}=7，所以有表3：
第三遍：F(4)=max{F(2)+c4,F(3)}=max{15,7}=15，所以有表4：
第五遍：F(5)=max{F(3)+c5,F(4)}=max{13,15}=15，所以有表5：
最大币值总和为15,。
而由于F(5)=F(4), F(4)=F(2)+c4，所以为最大币值总和硬币序列加上c4:{c4}；F(2)=F(1)，所以为最大币值总和硬币序列加上c1，得最终序列为{c1,c4}。
下面给出算法：
Step1. 根据硬币面值序列c1, c2, ..., cn ，设面值合计序列F(0), F(1), ...,F(n)，其中，记F(0)=0, F(1)=c1,k=1；
Step2. 计算F(k+1)，其中F(k+1)=max{F(k-1)+c(k+1),F(k)}
Step3. 若k+1小于n，返回Step2，否则，输出F(n)，算法结束。
以下是在matlab下编写的m文件代码：
function [result]=Code(A)
%%%%%%%%%%%%%%%
%输入：
% A： --硬币序列
%输出：
% result：
% result(1,1): --币值总和最大值
% result(1,2:end): --组成最大币值总和的硬币序列
%%%%%%%%%%%%%%%
n=size(A,2);
from=zeros(3,n+1);
from(1,2:n+1)=A;
from(1,1)=0;
from(2,1)=0;
from(2,2)=A(1,1);
k=2;
while(k1)
if(from(3,s)==s-1)
s=s-1;
else
B=[B,s];
s=s-2;
end
end
B=B-1;
result=[a,B];
end
算法效率：
算法的主要部分在于for循环部分，如下：
while(k<n+1)
from(2,k+1)=max(from(1,k+1)+from(2,k-1),from(2,k));
k=k+1;
end
而由于每次填表时利用的是表格前面的已知信息，所以每一句的时间复杂度为O(1)，
所以当套用循环用于填表时，时间复杂度为O(n)，即该算法的时间复杂度为O(n)。