# 动态规划

# 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];
	}

# 279 完全平方数

我难以理解 www，dp 还是太让人头大了。
核心思维叫「最后一步」。假设我在拼 i ，想象最后一个选的平方数是 j² （ j² ≤ i ）。那么：

最后一个选了 j² ，用掉 1 个
剩下的 i - j² ，也得用最少个平方数拼，也就是 dp[i - j²]

所以「最后选 j² 」这种方案，总数 = dp[i - j²] + 1 。
那 j 可以是 1、2、3…… 所有满足 j² ≤ i 的数，我枚举所有可能的最后一步，取最小的：

dp[i] = min( dp[i - 1²] + 1,
             dp[i - 2²] + 1,
             dp[i - 3²] + 1,
             ... )            (对所有 j² ≤ i)

为什么这样一定对？ 因为「拼 i 的最优方案」去掉最后一个平方数后，剩下的「拼 i−j²」也必须是最优的 —— 否则把剩下那部分换成更优的，整体就更优了，矛盾。这就是 DP 的「最优子结构」。你只要抓住这一句话，转移方程就不再神秘。

	class Solution {
	public:
	int numSquares(int n) {
	vector<int> dp(n + 1, INT_MAX);
	dp[0] = 0;
	for (int i = 1; i <= n; i++)
	{
	for (int j = 1; j * j <= i; j++)
	{
	dp[i] = min(dp[i], dp[i - j * j] + 1);
	}
	}
	return dp[n];
	}
	};

# 322 零钱兑换

现在稍微可以理解了。和上一题思路基本差不多，问题在于有个小坑，就是初始化不能为 INT_MAX，不然后面 + 1 会溢出。
为什么上一题不会溢出？因为上一题所有 n 都必然有解，不会存在某个 dp [n] 最终为 INT_MAX 的情况，而这题存在无解。
除此之外也要注意这题里的 coins 不一定是有序的。

	class Solution {
	public:
	int coinChange(vector<int>& coins, int amount) {
	int kinds = coins.size();
	vector<int> dp(amount + 1, INT_MAX - 1);
	dp[0] = 0;

	for (int i = 0; i <= amount; i++)
	{
	for (int j : coins)
	{
	if (j <= i) {
	dp[i] = min(dp[i], dp[i - j] + 1);
	}
	}
	}

	if (dp[amount] >= INT_MAX - 1) {
	return -1;
	} else {
	return dp[amount];
	}
	}
	};

# 139 单词拆分

能推出来这个状态转移方程就好做了（可惜推不出来）：
dp[i] = dp[j] && check(str(j, i))
意思是对于一个字符串，它的前 i 个字母组成的子串是否合法，等价于前 j 个是否合法且 j 到 i 这一段子串是否在词典里。

	class Solution {
	public:
	bool wordBreak(string s, vector<string>& wordDict) {
	unordered_set<string> st;
	for (string s : wordDict)
	{
	st.insert(s);
	}
	bool dp[301] = {};
	dp[0] = true;
	for (int i = 1; i < s.length() + 1; i++)
	{
	for (int j = 0; j < i; j++)
	{
	if (dp[j] && (st.find(s.substr(j, i - j)) != st.end())) {
	dp[i] = true;
	break;
	}
	}
	}
	return dp[s.length()];
	}
	};

这边用的普通数组，经过试错后发现诸如 bool dp[s.length() + 1] = {}; bool dp[s.length() + 1]; 这样的写法都会报错，前者是不能用不定长数组，后者是没初始化后面会运行错误。你也可以用 vector，会自动初始化，但是速度会慢一些。

原创