对待递推类的题目，具体问题，具体分析！递推算法首要问题是为了找到相邻数据项的关系——即递推关系。
递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了一个若干步连续的简单计算，递推算法也可以看成一种特殊的迭代算法！
【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
1、 一步可沿左斜线向下或右斜线向下走；
2、 三角形行数小于等于100；
3、 三角形中的数字为0，1，…，99；
测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
此题的解法有很多种，我们从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择肯定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的方法，设a[i][j]存放从i,j出发到达第n层的总和最大。则a[i][j] = max{a[i][j]+a[i+1][j] , a[i][j] + a[i+1][j+1]} 最大总和在a[0][0]处取得.
#include<iostream>
using namespace std ;
int main() {
int n ;
cin >> n ;
int a[100][100] ;
for(int i = 0 ; i < n ; i++ )
for( int j = 0 ; j < i+1 ; j++ )
cin >> a[i][j] ;
for( int ii = n-2 ; ii >= 0 ; ii-- )
for( int jj = 0 ; jj < ii + 1 ; jj++ ) {
if( a[ii+1][jj] > a[ii+1][jj+1] )
a[ii][jj] += a[ii+1][jj] ;
else
a[ii][jj] += a[ii+1][jj+1] ;
}
cout << a[0][0] << endl ;
return 0 ;
}
当n=3时，有如下3种铺法。
编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
面对上述问题，如果思考不当，若想获得问题的解答是相当困难的，可以用递推的方法归纳出问题解的一般规律。
当n=1时，只有一种铺法；
当n=2时，有两种铺法；
当n=3时，有三种铺法；
当n=4时，有五种铺法；
由此可以推出一般规律：f(n) = f(n-1)+f(n-2) ;
一般求f(n)时，如果第n个是竖着放，剩下有n-1个需要排列，这时排列方法数为f(n-1);
如果第n个是横着放的，剩下有n-2个需要排列，这时排列方法数为f(n-2);
所以：f(n) = f(n-1)+f(n-2) 就是问题求解的递推公式。
【例3】棋盘格数
设有一个N*M方格的棋盘（ l≤ N≤100，1≤M≤100）。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。
例如：当 N=2， M＝3时：
正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。
长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长方形有2个：3*2的长方形有1个：
程序要求：输入：N，M
输出：正方形的个数与长方形的个数
如上例：输入：2 3
输出：8 10
1、计算正方形的个数：s1
边长为1的正方形个数：n*m ；
边长为2的正方形个数：(n-1)*(m-1)
边长为3的正方形个数：(n-2)*(m-2)
………………
边长为min{n , m}的正方形个数：( n - ( min{n,m} - 1 ) ) * ( m - ( min{n,m} - 1 ) )
根据加法原理得出：
正方形的个数为：边长为1的个数 + 边长为2的个数 + 边长为3的个数 …… + 边长为min{n , m}的个数
2、长方形和正方形的个数之和：s
宽为1的长方形个数和正方形个数之和为：n ;
宽为2的长方形个数和正方形个数之和为：n - 1 ;
宽为3的长方形个数和正方形个数之和为：n - 2 ;
……………………
宽为m的长方形个数和正方形个数之和为：1 ；
长为1的长方形个数和正方形个数之和为：m；
长为2的长方形个数和正方形个数之和为：m - 1 ;
长为3的长方形个数和正方形个数之和为：m - 2 ;
……………………
长为n的长方形个数和正方形个数之和为：1 ；
根据乘法原理：s = (1+2+3+……+n) * (1+2+3+……+m)
3、长方形的个数：s2
s2 = s - s1 ;
#include<iostream>
using namespace std ;
int main() {
int n , m ;
while(cin >> n >> m) {
int s1 = 0 , s , s2 ;
for( int k = 1 ; k <= ( n > m ? m : n ) ; k++ )
s1 += (n-( k -1 )) * ( m-(k-1)) ;
int sum1 = 0 , sum2 = 0 ;
for( int i = 1 ; i <= n ; i++ )
sum1 += i ;
for( int j = 1 ; j <= m ; j++ )
sum2 += j ;
s = sum1 * sum2 ;
s2 = s - s1 ;
cout << s1 << " " << s2 << endl ;
}
return 0 ;
}
考虑这种问题一般从第n-1位推导第n位，且当前位是取偶数个还是奇数个。
可以用a[i][0]表示前i位取偶数个3有几种情况，用a[i][1]表示前i位取奇数个3有几种情况；
则状态转移方程可以表示为：
a[i][0] = a[i-1][0] * 9 + a[i-1][1] ;
a[i][1] = a[i-1][0] + a[i-1][1] * 9 ;
当位数大于1时，第一位不能为0，所以第一位只能有九种取法。
#include<iostream>
#include<stdio.h>
using namespace std ;
int main() {
int n ;
cin >> n ;
int a[100][2] , x ;
a[1][0] = x = 9 ;
a[1][1] = 1 ;
for(int i = 2 ; i <= n ; i++){
if(i == n)
x = 8 ;
a[i][0] = a[i-1][0] * x + a[i-1][1] ;
a[i][1] = a[i-1][1] * x + a[i-1][0] ;
}
cout << a[n][0] << endl ;
return 0 ;
}
#include<iostream>
#include<stdio.h>
using namespace std ;
int main() {
int m ,n , x , y ;
cin >> m >> n >> x >> y ;
int dp[100][100] ;
for(int ii = 0 ; ii <= m ; ii++)
for(int jj = 0 ; jj <= n ; jj++)
dp[ii][jj] = 1 ;
dp[0][0] = 1 ;
dp[x][y] = 0 ;
dp[x+1][y+2] = 0 ;
dp[x+1][y-2] = 0 ;
dp[x+2][y+1] = 0 ;
dp[x+2][y-1] = 0 ;
dp[x-1][y+2] = 0 ;
dp[x-1][y-2] = 0 ;
dp[x-2][y+1] = 0 ;
dp[x-2][y-1] = 0 ;
for(int i = 0 ; i <= m ; i++ )
for(int j = 0 ; j <= n ; j++) {
if(!dp[i][j]) continue ;
if(!i&&!j) continue ;
else if(i == 0) dp[i][j] = dp[i][j-1] ;
else if(j== 0) dp[i][j] = dp[i-1][j] ;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1] ;
}
cout << dp[m][n] << endl ;
return 0 ;
}
原文：http://blog.csdn.net/ding_hai_long/article/details/20231773