定义dp[i]为爬到i所需最少成本，dp[0]、dp[1]是边界，为0，状态转移：从下往上看每个阶梯，每个阶梯能从i-1或i-2上来，对应最少成本为：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])；最后返回dp.back()；

注：此题因为只用到了dp[i]、dp[i - 1]和dp[i - 2]，不如用res、pre和prepre存储，可以减少空间使用。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int res;int prepre = 0, pre = 0;for (int i = 2; i <= cost.size(); ++i) {res = min(pre + cost[i - 1], prepre + cost[i - 2]);prepre = pre;pre = res;}return res;}
};

和爬楼梯很像，定义dp[i]为0~i房子能偷到的最多金额，每个房子只能选择偷（=dp[i - 2] + nums[i]）或不偷（直接=dp[i - 1]），取最大值即可，即dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])；最后返回dp.back()；

同样可以和上一题一样减少空间使用，但是记得判好nums.size() < 3 的特殊情况。

class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if (len == 1) return nums[0];if (len == 2) return max(nums[0], nums[1]);int res;int prepre = nums[0];int pre = max(nums[0], nums[1]);for (int i = 2; i < len; ++i){res = max(pre, prepre + nums[i]);prepre = pre;pre = res;}return res;}
};

最简单的办法就是偷环形起始的第一家与偷第二家分成两种情况，各dp一遍。

即0~len - 2偷一遍，1~len - 1偷一遍，需要注意的是只有仨数的时候for循环根本进不去，所以提前吧res1和res2置为仨数时该有的值。

以下第二个代码顺便把空间简化了一下。

class Solution {
public:int rob(vector<int> &nums) {int len = nums.size();if (len == 1) return nums[0];else if (len == 2) return max(nums[0], nums[1]);vector<int> dp(len);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < len - 1; ++i) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}vector<int> dp2(len);dp2[0] = 0;dp2[1] = nums[1];for (int i = 2; i < len; ++i) {dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);}return max(dp[len - 2], dp2[len - 1]);}
};class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if (len == 1) return nums[0];else if (len == 2) return max(nums[0], nums[1]);int prepre = nums[0];int pre = max(nums[0], nums[1]);int res1 = prepre; // len 为3时不会进循环，保证res1是有值的for (int i = 2; i < len - 1; ++i) {res1 = max(prepre + nums[i], pre);prepre = pre;pre = res1;}prepre = nums[1];pre = max(nums[1], nums[2]);int res2 = nums[1]; // len为3时不会进循环，保证res2是有值的for (int i = 3; i < len; ++i) {res2 = max(prepre + nums[i], pre);prepre = pre;pre = res2;}return max(res1, res2);}
};

还是简单的按顺序就能找到子问题：一次刷一个房子，可以刷三种颜色，我们可以动态规划第i个房子刷某种颜色要花的最小成本。刷0色需要的最小花费就是前一项dp中另外两种颜色更小的花费。直接看代码吧：

注：这里发现dp多了一个维，因为之前两个问题，不管你走一个还是走两个楼梯，偷这个还是不偷这个房子，最后的结果都是单一的成本或者单一的金额，楼梯还是楼梯，住户还是住户。但这道题，每次的结果房子也有不同变化，也就是说：“最后的最小成本是随着房子粉刷颜色的不同而变化的”，除了房子是第几个（i位置），当前房子要涂成的颜色也影响最终的结果，因此需要多加一个维。

class Solution {
public:int minCost(vector<vector<int>>& costs) {int len = costs.size();if (len == 1) return min(min(costs[0][0], costs[0][1]), costs[0][2]);vector<vector<int>> dp(len, vector<int>(3));vector<int> res(3);vector<int> pre(3);for (int i = 0; i < 3;  ++i) {pre[i] = costs[0][i];}for (int i = 1; i < len; ++i) {res[0] = costs[i][0] + min(pre[1], pre[2]);res[1] = costs[i][1] + min(pre[0], pre[2]);res[2] = costs[i][2] + min(pre[1], pre[0]);pre = res;}return min(min(res[0], res[1]), res[2]);}
};

很不容易遇到会做的，哭死。

这个就是简单的单步问题了，每走一步都是上一步的路径数加1，有从上面走下来和从左边走过来两种，加起来就好。

class Solution {
public: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.back().back();}
};

简单单步问题，和上一题类似，每一步就是当前grid值加上上一步最小的dp值。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n));dp[0][0]= grid[0][0];for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];for (int i = 1; i < n; ++i) dp[0][i] = dp[0][i - 1] + grid[0][i];for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);}}return dp.back().back();}   
};

同样是简单的单步问题，边界就是三角形的左边和右边，都只能从上往下一溜下来。

但中间的可以选是从dp[i - 1][j]还是 dp[i - 1][j - 1]下来，三角形也别担心，就是一个没填满的矩阵罢了：

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();vector<vector<int>> dp(n, vector<int>(n));dp[0][0] = triangle[0][0];for (int i = 1; i < n; ++i) dp[i][0] = dp[i - 1][0] + triangle[i][0];for (int i = 1; i < n; ++i) dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];for (int i = 2; i < n; ++i) {for (int j = 1; j < i; ++j) {dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1]);}}return *min_element(dp[n - 1].begin(), dp[n - 1].end());}
};

这次从头开始看，每一次的选择就是变0和变1，但是这没办法达到题目要求的“递增顺序”。

这就引出“以此结尾”类的dp问题。我们变0变1没法决定变到递增顺序的子问题，但是可以做成：“i处以0/1结尾所需要的最少翻转次数”。

这就有了子问题了。以0结尾只需要看当前位s是否为1，和前一位dp，以1结尾需要看前一位以0结尾和以1结尾的更小值继续更新，直接看代码：

class Solution {
public:int minFlipsMonoIncr(string s) {int len = s.size();vector<vector<int>> dp(len, vector<int>(2));dp[0][0] = (s[0] == '0' ? 0 : 1);dp[0][1] = (s[0] == '1' ? 0 : 1);for (int i = 1; i < len; ++i){dp[i][0] = dp[i - 1][0] + (s[i] == '0' ? 0 : 1);dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '1' ? 0 : 1);}return min(dp[len - 1][0], dp[len - 1][1]);}
};

我都放在这了，相比也猜得到，这也是“以此结尾”类，很自然的想定义dp][i]为以i结尾的所有元素能组成的最长斐波那契子列长度。但再好好看下题，上一题以i结尾，且需要把结尾分成两种情况，也就是以0 / 1结尾，我们这里以什么结尾呢？以i结尾，但是斐波那契子列需要至少两个数才能决定（第三个数可以通过差值是否在arr内和是否非法）。所以我们有了：“以i结尾且上一斐波那契数为 j (j ∈ (0, i)) 组成的最长斐波那契子列长度”。j最大是 len - 1 ，因此可以定义dp[j][i]（len - 1行、len列）这么一个数组，（虽然会有将近一半空间浪费掉），为了判断差值是否在arr内，我们维护一个无序map，存储{arr[i], [i]}，以供查询。

那么代码就出来了：

class Solution {
public:int lenLongestFibSubseq(vector<int> &arr) {int len = arr.size();if (len == 3) return ((arr[0] + arr[1] == arr[2]) ? 3 : 0);unordered_map<int, int> mp;for (int i = 0; i < len; ++i) mp.emplace(arr[i], i);vector<vector<int>> dp(len - 1, vector<int>(len, 2));int ans = 0;for (int i = 2; i < len; ++i) {for (int j = i - 1; j > 0; --j) {int diff = arr[i] - arr[j];if (mp.count(diff) && mp[diff] < j) {dp[j][i] = max(dp[j][i], dp[mp[diff]][j] + 1);ans = max(ans, dp[j][i]);}}}return ans;}
};

如果你看到了请再去重做一遍

稍微想一下就发现，我们的方案里面都很想知道，原始s里面任意i到j（0<=i < j<len）是否回文子列。这里有一个很巧妙的拿到这个数据的方法：

i到j要是回文串，首先得满足两边字符相同，相同的话再看他们中间是不是回文串，如cabac，两边字符相同，是否回文串只需看中间是不是回文串

vector<vector<bool>> f(len, vector<bool>(len, true)); // f[i][j]: if s(i...j) substr is palindrome
// for (int i = 0; i < len; ++i) f[i][i] = true; // 没必要了
for (int i = len - 2; i >= 0; --i) {for (int j = i + 1; j < len; ++j) {f[i][j] = (s[i] == s[j] && f[i + 1][j - 1]);}
}

相当于已经做了一次dp了，算是预处理，现在我们知道了s中所有回文子串的位置，接下来又是一个很难想到的套路：

定义dp[i]为0~i最小分割次数，直接看代码吧我自己还没理解彻底透彻所以很难讲清楚：

vector<int> dp(len, INT_MAX);
for (int i = 0; i < len; ++i) {if (f[0][i]) {dp[i] = 0;} else {for (int j = 0; j < i; ++j) {if (f[j + 1][i]) {dp[i] = min(dp[i], dp[j] + 1);}}}
}

所有代码：

class Solution {
public:int minCut(string s) {int len = s.size();if (len == 1) return 0;vector<vector<bool>> f(len, vector<bool>(len, true)); // f[i][j]:if s(i...j) substr is palindromefor (int i = len - 2; i >= 0; --i) {for (int j = i + 1; j < len; ++j) {f[i][j] = (s[i] == s[j] && f[i + 1][j - 1]);}}vector<int> dp(len, INT_MAX);dp[0] = 0;for (int i = 1; i < len; ++i) {if (f[0][i]) {dp[i] = 0;} else {for (int j = 0; j < i; ++j) {if (f[j + 1][i]) {dp[i] = min(dp[i], dp[j] + 1);}}}}return dp[len - 1];}
};

如果你看到了请再去重做一遍

话不多说看题解：

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int len1 = text1.size(), len2 = text2.size();vector<vector<int>> dp(len2 + 1, vector<int>(len1 + 1));for (int i = 0; i < len1; ++i) dp[0][i] = 0;for (int i = 1; i < len2; ++i) dp[i][0] = 0;for (int i = 1; i <= len2; ++i) {for (int j = 1; j <= len1; ++j) {if (text1[j - 1] == text2[i - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp.back().back();}
};

这是图解，自己理解一下：

如果你看到了请再去重做一遍

最后的图解是路径，很有意思；

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();if (len1 + len2 != len3) return false;vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));dp[0][0] = true;for (int i = 0; i <= len1; ++i) {for (int j = 0; j <= len2; ++j) {if (i > 0 && s1[i - 1] == s3[i + j - 1]) {dp[i][j] = dp[i - 1][j] | dp[i][j];}if (j > 0 && s2[j - 1] == s3[i + j - 1]) {dp[i][j] = dp[i][j - 1] | dp[i][j];}}}return dp.back().back();}
};

如果你看到了请再去重做一遍

这次是s[i:]，代表i到结尾的子序列，唉。

这题还有个BUG，本来int就能过，然后Leetcode用例又多加了几个贼长的，现在必须unsigned long long才能过了

class Solution {
public:int numDistinct(string s, string t) {int sSize = s.size();int tSize = t.size();if (tSize > sSize) return 0;vector<vector<unsigned long long>> dp(sSize + 1, vector<unsigned long long>(tSize + 1, 0));for (int i = 0; i <= sSize; ++i) dp[i][tSize] = 1;// for (int i = 0; i <= tSize; ++i) dp[sSize][i] = 0; // 没必要for (int i = sSize - 1; i >= 0; --i) {for (int j = tSize - 1; j >= 0; --j) {dp[i][j] = dp[i + 1][j] + ((s[i] == t[j])? dp[i + 1][j + 1] : 0);} }return (int)dp[0][0];}
};

理解：

s[i]与t[j]不同，那s[i]与t[j]不可能匹配，只能看看s[i]后面的子列能不能涵盖到t[i:]，即dp[i][j] = dp[i + 1][j]；

s[i]与t[j]相同，那s[i]与t[j]是可能匹配的，除了后面的子列能涵盖到t[j:]的数量外，还要加上s[i:]能涵盖t[j:]的数量，而当前字符是相同的，只需要看他俩后面s[i+1:]能涵盖t[j+1:]的数量，即再加上dp[i + 1][j + 1]。

复习警告

经典dp题，我确实想不到用sumHalf作dp的一维

using namespace std;
class Solution {
public:bool canPartition(vector<int> &nums) {int len = nums.size();if (len < 2) return false;int sum = accumulate(nums.begin(), nums.end(), 0);if (sum & 1) return false;int maxNum = *max_element(nums.begin(), nums.end());int sumHalf = sum >> 1; // 即 sum / 2if (maxNum > sum) return false; // 这里别看错了，是要与sumHalf比较else if (maxNum == sum) return true;vector<vector<bool>> dp(len, vector<bool>(sumHalf + 1, false));// 定义dp[i][j]为0-i下标内是否能选出数个元素（可为零个）使得和为jfor (int i = 0; i < len; ++i) dp[i][0] = true;dp[0][nums[0]] = true;for (int i = 1; i < len; ++i) {int num = nums[i];for (int j = 1; j <= sumHalf; ++j) {if (num > j) dp[i][j] = dp[i - 1][j];else dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];}}return dp[len - 1][sumHalf];}
};

复习警告

和101分割等和子集很像，稍微用点数学公式：

p记为+的和，n记为-的和，要求是：p - n = target, p + n = sum；

合起来即为：p = (target + sum) / 2；

也就是看nums里面有没有数个数字使得和为(target + sum) / 2；

但照搬过来需要改不少东西，因为0有很大影响；

using namespace std;
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int len = nums.size();if (len == 1) return ((nums[0] == abs(target))? 1 : 0);vector<int> numsNoZero;for(int i = 0; i < len; ++i) if(nums[i])numsNoZero.emplace_back(nums[i]);int sum = accumulate(nums.begin(), nums.end(), 0);if ((sum + abs(target)) & 1) return 0;int ourTarget = (sum + abs(target)) >> 1;int maxNum = *max_element(nums.begin(), nums.end());if (maxNum > ourTarget) return 0;int zeroCnt = 0;for (int i = 0; i < len; ++i) if (nums[i] == 0) zeroCnt++;if (len - zeroCnt == 1) return (sum == ourTarget ? 1 : 0) * pow(2, zeroCnt);else if (len - zeroCnt == 0) return pow(2, zeroCnt);len = numsNoZero.size();vector<vector<int>> dp(len, vector<int>(ourTarget + 1));for (int i = 0; i < len; ++i) dp[i][0] = 1;dp[0][numsNoZero[0]] = 1;for (int i = 1; i < len; ++i) {int num = numsNoZero[i];for (int j = 1; j <= ourTarget; ++j) {if (num > j) dp[i][j] = dp[i - 1][j];else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];}}return dp[len - 1][ourTarget] * pow(2, zeroCnt);}
};

倒是还有一个比较容易想到的：直接复用分割等和子集的思路，就是空间占用高了一倍不止，速度也慢：

因为每次当前数字只能选择加或减，那也就只有两种情况：看j + num和j - num在不在范围里，其中j的取值在[-sum, sum]，当然数组没有负数索引，我们需要加一个sum的偏移量，直接看代码：

class Solution {
public:int findTargetSumWays(vector<int> &nums, int target) {int len = nums.size();int targetAbs = abs(target);if (len == 1) return ((nums[0] == targetAbs) ? 1 : 0);int sum = accumulate(nums.begin(), nums.end(), 0);if (sum < targetAbs) return 0; // 全取正号或符号也达不到目标，直接pass，否则后面数组会越界vector<vector<int>> dp(len, vector<int>(sum + sum + 1));dp[0][nums[0] + sum] += 1; dp[0][-nums[0] + sum] += 1;for (int i = 1; i < len; ++i) {int num = nums[i];for (int j = -sum; j <= sum; ++j) {if (j + num >= -sum && j + num <= sum) {dp[i][j + sum] += dp[i - 1][j + num + sum];}if (j - num >= -sum && j - num <= sum) {dp[i][j + sum] += dp[i - 1][j - num + sum];}}}return dp[len - 1][target + sum];}
};