# 动态规划

# 62 不同路径

注意到第一行和第一列的点的路径固定为 1
没有优化空间的方法：

	int uniquePaths(int m, int n)
	{
	vector<vector<int>> dp(m, vector<int>(n));
	for (int i = 0; i < m; i++)
	{
	dp[i][0] = 1;
	}
	for (int i = 0; i < n; i++)
	{
	dp[0][i] = 1;
	}
	for (int i = 1; i < m; i++)
	{
	for (int j = 1; j < n; j++)
	{
	dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
	}
	}
	return dp[m - 1][n - 1];
	}

此外优化空间的方法：
据观察，当前状态只与前一个数状态与上方的数字状态有关系。因此，我们实际上只用存储一行的数据，更新时，由前一个数据与旧的当前位置的数据相加，即可得到新数据。

	int uniquePaths(int m, int n)
	{
	vector<int> dp(n, 1);

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

# 63 不同路径 II

多了一个障碍物。
明确：有障碍物的位置可能路径直接为 0. 此外需要特判第一个位置。
另外这里实际上有个点：也就是第一列，我们不手动更新（只有当这里是有石头时，更新成 0），当从上到下循环时，循环内其实就自动继承了第一个点上一行的值。

	int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
	{
	int m = obstacleGrid.size();
	int n = obstacleGrid[0].size();
	vector<int> dp(n, 0);
	if (obstacleGrid[0][0] == 1)
	{
	return 0;
	}
	else
	{
	dp[0] = 1;
	}
	for (int i = 0; i < m; i++)
	{
	for (int j = 0; j < n; j++)
	{
	if (obstacleGrid[i][j] == 1)
	{
	dp[j] = 0;
	}
	else if (j > 0)
	{
	dp[j] += dp[j - 1];
	}
	}
	}
	return dp[n - 1];
	}

# 198 打家劫舍

主要是这个状态转移方程得搞懂是为什么。

$dp[i]=max(dp[i−2]+nums[i],dp[i−1])$

$dp[x]$ 的定义是 “面对前 $x$ 间房时，所能偷到的最大金额”。
为什么 $dp[i-2]$ 保证是最大的？
根据定义：在前 $i-2$ 间房的范围内能拿到的最大金额，恰好、正好、不多不少就是 $dp[i-2]$ ！
你可能会有一个隐忧：“万一我在前 $i-2$ 间房里，其实为了利益最大化，并没有偷第 $i-2$ 间，而是偷了第 $i-3$ 间呢？ $dp[i-2]$ 还能代表最大吗？” 答案是：能。 因为 $dp[i-2]$ 的定义不是 “必须偷第 $i-2$ 间房的最大收益”，而是 “考虑前 $i-2$ 间房的最大收益”。不管它内部是怎么选的（偷了 $i-2$ ，或者跳过了 $i-2$ 保留了 $i-3$ 的收益）， $dp[i-2]$ 这个变量已经通过它自己的状态转移，把那段历史的最优解锁定在里面了。

	int rob(vector<int> &nums)
	{
	int n = nums.size();
	if (n == 1)
	{
	return nums[0];
	}
	vector<int> maxnums(n, 0);
	maxnums[0] = nums[0];
	if (n >= 2)
	{
	maxnums[1] = max(nums[0], nums[1]);
	}

	for (int i = 2; i < n; i++)
	{
	maxnums[i] = max(maxnums[i - 1], maxnums[i - 2] + nums[i]);
	}
	return maxnums[n - 1];
	}

原创

# 动态规划

# 62 不同路径

# 63 不同路径 II

# 198 打家劫舍

我笔下的他们

BFS 和 DFS