25 动态规划DP--递推求解

题目来源

2008年华中科技大学计算机保研机试真题

题目描述

N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）

输入说明

输入包括一个整数N,(1<=N<90)。

输出说明

可能有多组测试数据，对于每组数据， 输出当楼梯阶数是N时的上楼方式个数。

样例展示

输入：
4
复制
输出：
5

问题分析

这个问题就是一个典型的递推问题。若我们把N分别等于1，2，3...的答案依次排列成一个数列，我们即需求这个数列每一个数的值。我们定义f[n]为数列中的第n个数字，同时F[n]为台阶总数为n时的上台阶方式总数。首先，我们必须确定数列之间的递推关系。当n大于2时，我们考虑每一种上台阶方式的最后一步，由于只有两种行走的方法，因此它只可能是从n-1阶经过一步走到n阶，或者从n-2阶经过2步走到n阶。我们分别考虑这两种走法，即我们将此时所有的上台阶方式按照最后一步走法的不同分为两类，分别确定这两类的上台阶数目。这样我们就确定达到n阶楼梯总的上楼方式个数为F[n-1]和F[n-2]的和，即F[n]=F[n-1]+F[n-2]。这就是我们这个数列的递归关系。由初始值F[1]=1,F[2]=2,我们就能得到所有F[n]的值。

C++代码

#include<iostream>
using namespace std;

typedef long long ll;

ll F[100];

int main() {
    F[1]=1;
    F[2]=2;
    for(int i=3;i<=90;i++) {
        F[i]=F[i-1]+F[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF) {
        printf("%lld\n",F[n]);
    }
    return 0;
}

不容易系列之一

题目描述

大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语 考试的时候，竟然把 40 个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。不幸的是，这种小概率事件又发生了，而且就在我们身边： 事情是这样的——HDU 有个网名叫做 8006 的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给 n 个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！现在的问题是：请大家帮可怜的 8006 同学计算一下，一共有多少种可能的错误方式呢？

输入说明

输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数 n（1<n<=20），n 表示 8006 的网友的人数。

输出说明

对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。

样例说明

样例输入：
2
3
样例输出：
1
2

问题分析

同样的，在该例子中我们也容易得到规模较小时的错装方式数量。如n为1时，数量为0;n为2时数量为1.我们按照n的取值顺序将所有的错装方式数量排列为一个数列，同样F[n]表示数列里第n个数的取值，F[n]同时代表n个信封的错装方式总数。

接下来我们确定该数列的递推关系。当n大于3时候，我们考虑n封信全部装错的情况。将信封按照顺序由1到n编号。在任意一种封装方案中，假设n号信封里面装的是k号信封的信，而n号信封里的信则封装在m号信封里。我们按照k和m的相等与否将总的装错方式分为两类。

若k不等于m，交换n号信封和m号信封的信后，n号信封里装的恰好是对应的信，而m号信封中错装k号信封的信，即除n号信封外其余n-1个信封装错，其装错方式为F[n-1]，又由于m的n-1个可能取值，这类错装总数为（n-1）F[n-1]。也可以理解为，在n-1个信封错装的F[n-1]的基础上，将n号信封所装的信与n-1个信封中任意一个信封交换后，得到所有信封的全部装错的方式数。

另一种情况，若k等于m,交换n号信封和m号信封后，n和信封和m号信封里面装的恰好是对应的信，这样除她们之外剩余的n-2个信封全部错装，其错装方式为F[n-2]，又由于m的n-1个取值，这类错装方式总数为（n-1）* F[n-2]。也可以理解为，在n-2个信封全部错装的基础上，交换最后两个信封中的信（n号信封和1到n-1号信封中任意一个）共有n-1种选择，使得所有的信封全部错装的方式数。

综上所述：F[n]=(n-1) * F[n-1] + (n-1) * F[n-2]

C++代码

#include<iostream>
using namespace std;

typedef long long ll;
ll F[21];

int main() {
    F[1]=0;
    F[2]=1;
    for(int i=3;i<=20;i++) {
        F[i]=(i-1)*F[i-1]+(i-1)*F[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF) {
        printf("%lld\n",F[n]); //输出
    }
    return 0;
}

吃糖果

https://www.nowcoder.com/questionTerminal/72015680c32b449899e81f1470836097

C++代码

//话说这应该是和爬楼梯一样吧
#include<iostream>
using namespace std;

typedef long long ll;

ll dp[21];
int main() {
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=20;i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    int n;
    while(scanf("%d",&n)!=EOF) {
        printf("%d\n",dp[n]);
    }
    return 0;
}