矩阵从左上角走到右下角（dp） |
您所在的位置：网站首页 › 1112等于多少 › 矩阵从左上角走到右下角（dp） |
|
1、有多少种走法 在NxM的方格中，以左上角格子为起点，右下角格子为终点，每次只能向下走或者向右走，请问一共有多少种不同的走法给定两个正整数int n,int m，请返回走法数目。方法1：思想：dp[n][m]=dp[n-1][m]+dp[n][m-1]表示走到（n,m）位置的走法等于走到(n-1,m)(左边)加上(n,m-1)（上方）的和，用递归的思想可以做出 int way(int i,int j){ if (i == 0 )//位于某一行，只有j种方法 return j; else if (j == 0)//位于某一列，有i种方法 return i; return way(nums, i - 1, j) + way(nums, i, j - 1); }方法2：组合问题：一共要走（n-1）+（m-1）次其中有（n-1）次要选择向下走，当选者好向下走的位置后向右走的位置也随之确定，即dp[n][m] = C(n+m-2, n-1)，同理有（m-1）次选择向右走即dp[n][m] dp[n][m] = C(n+m-2, n-1) 故：dp[n][m] = C(n+m-2, n-1) = C(n+m-2, m-1) int uniquePaths(int m, int n) { int N = n + m - 2; int K = n - 1; double res = 1.0; for (int i = 1; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |