A robot is located at the top-left corner of amxngrid(marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. Therobot is trying to reach the bottom-right corner of the grid (marked ‘Finish’in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note:mandnwillbe at most 100.
HideTags
ArrayDynamic Programming
#pragma once#include<iostream>using namespace std;//法1：递归，超时int uniquePaths1(int m, int n) {if (m == 2 || n == 2)return m+n-2;return uniquePaths1(m – 1, n) + uniquePaths1(m, n – 1);}//法2：数学公式 求m+n-2中取m-1的组合数int uniquePaths2(int m, int n){long long result = 1;int reduce = m – 1;for (int i = m – 1; i >= 1; i–){result *= (n – 1 + i);while (reduce>0 && result%reduce == 0){result = result / reduce;reduce–;}}//内层循环用while后，由于最后结果一定是能整除的，所以不用再加以下/*while (reduce > 0){result = result / reduce;}*/return result;}void main(){cout << uniquePaths2(36, 7) << endl;cout << uniquePaths1(36, 7) << endl;system("pause");}
，贪婪是最真实的贫穷，满足是最真实的财富
