写在前面
动态规划的题目主要的步骤是：
- 搭记忆化搜索+DFS框架
- 明确递推的方程，从后往前推
- 明确递归的边界，明确记忆化的数组的尺寸
但是很多复杂的题目，实际上要涉及到二维，边界的考量因素比较困难，如果递推关系都找不出来，那更加麻烦，只能说是要慢慢积累
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 C++实现
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> vis(n, -1);
function<int(int)> dfs = [&](int i){
if(i < 0) return 0;
if(vis[i] != -1) return vis[i];
int& res = vis[i];
res = max(dfs(i-1), dfs(i-2) + nums[i]);
return res;
};
return dfs(n-1);
}
};
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2
输入：n = 13 输出：2 解释：13 = 4 + 9
C++实现
class Solution {
public:
int numSquares(int n) {
vector<int> vis(n+1, INT_MAX);
function<int(int)> dfs = [&](int k){
if(k < 0) return INT_MAX;
if(k == 0) return 0;
if(vis[k] != INT_MAX) return vis[k];
int& res = vis[k];
for(int i = 1; i * i <= k; i++){
res = min(res, dfs(k - i * i) + 1);
}
return res;
};
return dfs(n);
}
};
注意，本题灵神用的是二维，但是我的就还是用一维。都可以，因为本题状态可以关联。
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2
输入：coins = [2], amount = 3 输出：-1
C++实现
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<int>> vis(n, vector<int>(amount+1, -1));
function<int(int, int)> dfs = [&](int i, int c){
if(i < 0) return c == 0 ? 0 : INT_MAX / 2;
if(vis[i][c] != -1) return vis[i][c];
int& res = vis[i][c];
if(coins[i] > c){
res = dfs(i - 1, c);
return res;
}
res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
return res;
};
int ans = dfs(n-1, amount);
return ans == INT_MAX / 2 ? -1 : ans;
}
};
这个写法的边界非常需要注意，个人觉得本题在动态规划中属于细节多的： 初始vis矩阵不可以设置为INT_MAX/2，原因是一旦没有解，
res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
dfs(i - 1, c)会一直返回INT_MAX/2，导致res一直是INT_MAX/2， 从而if(vis[i][c] != INT_MAX/2)这个判断就是形同虚设
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。 示例 2
输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意，你可以重复使用字典中的单词。
C++实现
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
int n = s.length();
vector<int> memo(n + 1, -1);
auto dfs = [&](this auto&& dfs, int i)->bool{
if(i == 0) return true;
if(memo[i] != -1) return memo[i];
int& res = memo[i];
for(int j = i - 1; j >= 0; j--){
string str = s.substr(j, i - j);
if(words.count(str) && dfs(j)){
return res = true;
}
}
return res = false;
};
return dfs(n);
}
};
注意的点是，这里面推荐用auto，不然显式去指定function<bool(int)>我们的记忆化搜索数组无法复用，既要存储bool的结果，又要用-1去判断是否访问过。
300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2
输入：nums = [0,1,0,3,2,3] 输出：4
C++实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> vis(n, -1);
auto dfs = [&](this auto&& dfs, int i)->int{
if(vis[i] != -1) return vis[i];
int& res = vis[i];
int tmp = 0;
for(int j = i - 1; j >= 0; j--){
if(nums[i] > nums[j]){
tmp = max(tmp, dfs(j));
}
}
return res = tmp + 1;
};
int ans = 0;
for(int i = 0; i < vis.size(); i++){
ans = max(ans, dfs(i));
}
return ans;
}
};
这个经典的题目，我反复刷了好几遍，我认为主要的难点是在于：
- 本题本身的关联不是直接的递推，需要for循环中逐个调用比较
- 需要遍历后再+1，如果冒失做更新，结果很容易搞混乱
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
C++实现
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2) return false;
int target = sum / 2;
int n = nums.size();
vector memo(n, vector<int>(target + 1, -1));
auto dfs = [&](this auto&& dfs, int i, int c)->bool{
if(i < 0) return c == 0;
int& res = memo[i][c];
if(res != -1) return res;
if(c < nums[i]){
return res = dfs(i - 1, c);
}
return res = dfs(i - 1, c) || dfs(i - 1, c - nums[i]);
};
return dfs(n - 1, target);
}
};
本题和零钱兑换挺相似的，但是要保证一下A出来，还是不简单的
32. 最长有效括号
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 “(()())”。
示例 1
输入：s = “(()” 输出：2 解释：最长有效括号子串是 “()”
示例 2
输入：s = “)()())” 输出：4 解释：最长有效括号子串是 “()()” 示例 3：
C++实现
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
vector<int> vis(n, -1);
auto dfs = [&](this auto&& dfs, int i)->int{
if(i < 0) return 0;
int& res = vis[i];
if(vis[i] != -1) return vis[i];
if(s[i] == ')'){
if(i > 0 && s[i-1] == '(') {
return res = dfs(i-2) + 2;
}
if(i >= dfs(i-1) + 1 && s[i - dfs(i-1) - 1] == '('){
return res = dfs(i-1) + 2 + dfs(i - dfs(i-1) - 2);
}
}
return res = 0;
};
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, dfs(i));
}
return ans;
}
};
本题的递推比较麻烦了，如果i-1是’(‘，或者说，i-1是’)’的情况下，去向前探测长度为dfs(i-1)的长度
- 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1
输入：m = 3, n = 7 输出：28
示例 2
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
class Solution {
public:
int uniquePaths(int m, int n) {
vector vis(m, vector<int>(n, -1));
function<int(int, int)> dfs = [&](int i, int j){
if(i == 0 || j == 0) return 1;
int& res = vis[i][j];
if(res != -1) return res;
res = dfs(i - 1, j) + dfs(i, j - 1);
return res;
};
return dfs(m - 1, n - 1);
}
};
本题在早期版本解法里面，i<0 || j<=0 返回0，并且给i=0,j=0赋值1， 这种设计方式我觉得不容易解释，且在面试中手撕很容易出问题， 所以我改了一版，因为肉眼分析得出第0行或第0列都是只有一种路线
64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2 输入：grid = [[1,2,3],[4,5,6]] 输出：12
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector vis(m, vector<int>(n, -1));
function<int(int, int)> dfs = [&](int i, int j){
if(i < 0 || j < 0) return INT_MAX;
int& res = vis[i][j];
if(res != -1) return res;
if(i == 0 && j == 0) return res = grid[0][0];
res = min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j];
return res;
};
return dfs(m - 1, n - 1);
}
};
本题的要注意的是边界这一块，出界就INT_MAX，但是特例是i = 0 && j == 0 就不需要特判了
1143. 最长公共子序列（经典）
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2
输入：text1 = “abc”, text2 = “abc” 输出：3 解释：最长公共子序列是 “abc” ，它的长度为 3 。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.length(), m = text2.length();
vector memo(n, vector<int>(m, -1));
auto dfs = [&](this auto&& dfs, int i, int j)->int{
if(i < 0 || j < 0) return 0;
int& res = memo[i][j];
if(res != -1){
return res;
}
if(text1[i] == text2[j]) return res = dfs(i - 1, j - 1) + 1;
return res = max(dfs(i - 1, j), dfs(i, j - 1));
};
return dfs(n - 1, m - 1);
}
};
