【无标题】

动态规划记录-----不同路径问题：

问题：有m*n的格子，每次只能向下或者向右移动一步。试图达到网格的右下角。 问总共有多少条不同的路径？
动态规划问题：比较重要的是思路和状态转移方程的确定，由题目可知：当到达某一格时，只能是向左或向右下来，例如当我们有2*2的表格，结果是由他的上一格和左边一格确定的，也就是左（1）+上（1）。所以推广，方程为vt[m,n]=vt[m-1]+vt[n-1];

class Solution {
public:
	int DWays(int m, int n)
	{
		//二维数组
		vector<vector<int>> vt(m, vector<int> (n));//vt里是方法数
		for (int i = 0; i < m; i++) vt[i][0] = 1;
		for (int i = 0; i < n; i++) vt[0][i] = 1;//边上的都为1
		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < n; j++)
			{
				vt[i][j] = vt[i - 1][j] + vt[i][j - 1];
			}
		}
		return vt[m - 1][n - 1];
	}
};

---