👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：线性dp
【概述】
线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案
👉⭐️第一题💎
✨题目
✨思路：
归，遍历所有的子数组，寻找和最大的一组，需要注意的是在该段代码中，递归出口如果设置为=0时return nums[index] 则在数组只有一个元素时需要去手动更新ans
✨代码：
class Solution { public: int process(vector<int> &nums, int index, int &ans) { if (index < 0) return 0; int tem = max(nums[index], nums[index] + process(nums, index - 1, ans)); ans = max(ans,tem); return tem; } int maxSubArray(vector<int> &nums) { int ans = INT_MIN; process(nums, nums.size() - 1,ans); return ans; } };
👉⭐️第二题💎
✨题目
300. 最长递增子序列
由暴力递归改成记忆化搜索，再通过打表优化成动态规划，这是一个二维dp。主要思想就是根据最长公共子序列模板，先将nums数组处理成严格递增的一个新数组nums1，然后寻找nums与nums1的最长公共子序列，得到的就是nums的严格递增序列
✨代码：
class Solution { public: int lengthOfLIS(vector<int> &nums) { set<int>tem(nums.begin(), nums.end()); vector<int> nums1(tem.begin(), tem.end()); vector<vector<int>> dp(nums.size() + 1, vector<int>(nums1.size() + 1)); for (int i = 1; i <= nums.size(); i++) { for (int j = 1; j <= nums1.size(); j++) { if (nums[i - 1] == nums1[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return dp[nums.size()][nums1.size()]; }; };
👉⭐️第三题💎
✨题目
✨代码：
class Solution { public: int dp(int index, int n,vector<int>&DP) {int tar = 1e9 + 7; if(DP[index])return DP[index]; if (index >= n) { DP[index] =1; return DP[index]; } DP[index]=(dp(index + 2, n,DP)%tar + dp(index + 1, n,DP)%tar)%tar; return DP[index]; } int countHousePlacements(int n) { int tar = 1e9 + 7; vector<int> DP(n+3); long long ans = dp(0, n,DP); long long A = (ans % tar) * (ans % tar)%tar; return A; } };
👉⭐️第四题💎
✨题目
✨思路：
看到这题我首先想到DFS，即将所有能走的路线都尝试一遍，如果最终能到达终点，则打印YES，然而思路虽然对了，但是对于这题来讲明显会超时，即使改记忆化搜索也没有用
但是很明显这道题并不需要dfs，只需按列遍历数组，如果同一列都是1，那么则无论如何都没有路，就直接打印NO即可，下面是先用DFS的暴力搜索代码，运行一般的测试用例没有错误，但是放到Oj上会TLE
✨代码：
#include <bits/stdc++.h> using namespace std; vector<vector<int>> dp; int pro(vector<string> &nums, int x, int y) { if (dp[x][y]) return dp[x][y]; if (nums[x][y] == '1') { dp[x][y] = 0; return dp[x][y]; } if (x == 1 && y == nums[0].size() - 1) { dp[x][y] = 1; return dp[x][y]; } int doo[][2] = {{0, 1}, {1, 0}, {1, 1}, {-1, 1}}; int X = x, Y = y; for (int i = 0; i < 4; i++) { x = x + doo[i][0]; y = y + doo[i][1]; if (x < 0 || x > 1 || y > nums[0].size() - 1) { x = X; y = Y; continue; } int f = pro(nums, x, y); if (f) { dp[x][y] = 1; return dp[x][y]; } } return dp[x][y]; } int main() { int n; cin >> n; while (n--) { int m; cin >> m; vector<string> nums(2); dp.resize(2, vector<int>(m)); for (int t = 0; t < 2; t++) { cin >> nums[t]; } int f = pro(nums, 0, 0); if (f) cout << "YES" << endl; else cout << "NO" << endl; dp.clear(); } system("pause"); return 0; }
- 更改后的正确代码
#include <bits/stdc++.h> using namespace std; int pro(vector<string> &nums) { for(int i=0; i<nums[0].size(); i++) { if(nums[0][i] == '1' && nums[1][i] == '1') return 0; } return 1; } int main() { int n; cin >> n; while (n--) { int m; cin >> m; vector<string> nums(2); for (int t = 0; t < 2; t++) { cin >> nums[t]; } int f = pro(nums); if (f) cout << "YES" << endl; else cout << "NO" << endl; } system("pause"); return 0; }
⭐️总结⭐️
动态规划其实就是暴力递归，最终优化成打表的形式，初学者可能不能立即推出状态转移方程，所以不妨先试试递归思想，试错的成本也很低
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
