#include <bits/stdc++.h> using namespace std; int n,m; int a[10001][10001]; int main(){ cin>>n>>m; a[0][1]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=a[i-1][j]+a[i][j-1]; } } cout<<a[n][m]; return 0; }

假设能有一种状态 dp[i][j] 表示从 (1, 1) 到达 (i, j) 不同路径的总量。那么 m*n 的网格从 (1, 1) 到达 (m, n) 不同路径的总量，就是 dp[m][n]。根据题意 dp[i][j] 作为一次阶段性终点，它只能： 从上面来：dp[i-1][j] 向下走 从左边来：dp[i][j-1] 向右走 因此： dp[i][j] = dp[i-1][j] + dp[i][j-1];

我们先看题目，发现这道题是道明显的动态规划题目。 我们先看思路： 问题背景 假设我们有一个m x n的网格，我们需要计算从左上角(1, 1)到右下角(m, n)的所有可能路径数。每次移动只能向右或向下。 动态规划解法 我们可以使用动态规划来解决这个问题。动态规划的核心思想是将大问题分解为小问题，并利用小问题的解来构建大问题的解。 状态定义 我们定义dp[i][j]为从起点(1, 1)到(i, j)的路径数。 状态转移方程 根据题意，到达(i, j)的路径数可以由以下两种情况得到： 1.从(i-1, j)向下移动一步到达(i, j)。 2.从(i, j-1)向右移动一步到达(i, j)。 初始化*重点 为了正确计算路径数，我们需要初始化第一行和第一列 1.对于第一行（即j=1的情况），到达任意点(i, 1)的唯一路径都是来自上边的点(i-1, 1)，因此第一行的所有点都应该初始化为1。 2.对于第一列（即i=1的情况），到达任意点(1, j)的唯一路径都是来自左边的点(1, j-1)，因此第一列的所有点也应该初始化为1。 重点：状态转移方程 题解： 给个赞吧！

这道题和A7998一样诶，那本狗搬一篇一模一样的过来完全可以吧？原题解 这道题用的是二维答案数组，最后只要对着坐标直接输出就行，但是，在数据处理和求状态转移方程上，这道题给本狗倒是挖了点坑...比如为啥小码君没把小蚂蚁直接踩死或者踩到左脚等等 开始正经讲题！ 1，数据处理方面 这道题题面上说这只蚂蚁只能向右边和上面走，而且要从右下角走到左上角，要知道，C++的数组结构是从左上角往右下角扩大的，那如果真按照题面来写的话，将会极其繁琐...(可能你代码没敲完，键盘先起义了）所以我们要先把题面倒一下，让这只蚂蚁从左上角往右下角走，只能向左或向下移动，被踩掉的是左脚 2.状态转移方程 这道题的状态转移方程其实和蜜蜂路线那道题差不多，这只小 蚂蚁如果想要到右下角（此时我们已经把题面倒了一下），那就必须得到右下角上方的格子或左边的格子，根据加法原理并以此类推，除了可以一次到达的格子外，所有格子的路径总数都为上方和左方的格子路径数之和，即a[i][j]=a[i-1][j]+a[i][j-1]; 3.敲键盘 现将一步到达的格子初始化，输入之后按照状态转移方程递推即可 记得开long long

动态规划(DP)写法 记得关注 推荐一下

#include<bits/stdc++.h> using namespace std; long long dp[105][105]; int n,m; int main(){ cin>>n>>m; for(int i=1;i<=m;i++) dp[i][1]=1; for(int i=1;i<=n;i++) dp[1][i]=1; for(int i=2;i<=m;i++){ for(int j=2;j<=n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } cout<<dp[m][n]; return 0; } 记得开LONG LONG！！！

#include<iostream> using namespace std; int i,j; int main() { int m,n; cin >> m >> n; long long f[m][n] = {0}; f[0][0] = 1; for(i=0; i<m; i++) { for(j=0; j<n; j++) { if(i == 0 && j == 0) continue; if(i-1 < 0) f[i][j] = f[i][j-1]; else if(j-1 < 0) f[i][j] = f[i-1][j]; else f[i][j] = f[i-1][j] + f[i][j-1]; } } cout << f[m-1][n-1] << endl; return 0; } 思想: 动态规划 状态转移方程为 走到这一格的方法数=走到上面的方法数+走到左边的方法数 即 f[i][j]=f[i-1][j]+f[i][j-1]

#include <bits/stdc++.h> using namespace std; long long dp[110]; //long long dp[110][110]; int main(){ long long n,m; cin>>n>>m; //dp[1][1]=1; dp[1]=1; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ // dp[i][j]=max(dp[i][j],dp[i-1][j]+dp[i][j-1]); dp[j]+=dp[j-1]; } } //cout<<dp[n][m]; cout<<dp[m]; return 0; }