方案数量

描述

给出一个N*M的棋盘，左下角坐标是（0，0），右上角坐标是（N，M），规定每次只能向上或者向右走，问从左下角走到右上角，一共有多少种方案。上图是一个4*3的棋盘。

输入

多组测试数据。
每组输入两个整数N，M（0≤N，M≤30）。
输入0,0时表示结束，不做任何处理。

输出

对于每组测试数据，输出对应的方案数。

样例输入

4 3
2 2
0 0

样例输出

35
6

分析：这道题有2种做法。

一、推公式

ans = C(n+m, n)。因为从左下角走到右上角一共要走n+m步，往上要走n步，如果用1表示向上走，用0表示向右走，则相当于给n+m个数进行赋值，其中n个数被赋值为1，求有多少种赋值方法。只需从n+m个数里挑出n个，有C(n+m, n)中挑选办法。

#include 
      
       

long long get_ans(long long a, long long x) {
    long long ans = 1;
    for(long long i = 1; i <= a; i++)
        ans = ans * (x - i + 1) / i;
    return ans;
}

int main() {
    long long n, m;
    while(~scanf("%lld%lld", &n, &m) && (n + m)) {
        printf("%lld\n", get_ans(n, n + m));
    }
    return 0;
}
      

二、递推

因为如果要到(n, m)点，要么从(n-1, m)点过来，要么从(n, m-1)点过来，设dp[i][j]表示从(0, 0)到(i, j)有多少种方案，

则dp[i][j] = dp[i-1][j] + dp[i][j-1]，最后输出dp[n][m]就是答案。

#include 
      
       
#include 
       
         const int N = 32; long long dp[N][N]; void get_ans() { memset(dp, 0, sizeof(dp)); for(int i = 0; i < 31; i++) dp[i][0] = dp[0][i] = 1; for(int i = 1; i < 31; i++) for(int j = 1; j < 31; j++) dp[i][j] = dp[i-1][j] + dp[i][j-1]; } int main() { get_ans(); int n, m; while(~scanf("%d%d", &n, &m) && (n + m)) { printf("%lld\n", dp[n][m]); } return 0; }
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： poj 递增栈 POJ2796 区间最大参考值 3250牛的视野

下一篇： NYOJ 1085 数单词 （AC自动机模板题）

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");