矩阵从左上角走到右下角（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 <= n - 1; ++i)
	{
		res = res * (N - K + i) / i;
	}
	return (int)res;
}

2、最小路径和/最大路径和

int dfs(vector<vector<int>>&A,int i, int j,int N,int M)
{

	if (i == N || j == M)
		return 0;
	else if (i == N - 1 && j == M - 1)
		return A[i][j];
	else
		return max(dfs(A,i + 1, j,N,M), dfs(A,i, j + 1,N,M)) + A[i][j];

}
int main()
{
    vector<vector<int>>nums = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 10, 11, 12, 13 } };
	int a = dfs(nums, 0, 0, 3, 4);
	cout << a << endl;
	getchar();
	return 0;
}

nt get_min(vector<vector<int>> nums, int n, int m)
{
	vector<vector<int>>dp(n, vector<int>(m, 0));
	dp[0][0] = nums[0][0];
	for (int i = 1; i < m; i++){
		dp[0][i] = dp[0][i - 1] + nums[0][i];
	}
	for (int i = 1; i < n; i++){
		dp[i][0] = dp[i - 1][0] + nums[i][0];
	}

	for (int i = 1; i < n; i++){
		for (int j = 1; j < m; j++){
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];
		}
	}
	return dp[n - 1][m - 1];

}

参考：