这道题比较简单，一开始写的递归，后来改成循环，发现都超时。写了一个简易版本的dp，如下所示：dp[i][j]定义：s1[1...i],s2[1...j]能否顺序匹配 s3[i+j]状态转移方程：有两种状态：1. dp[i][j] = dp[i-1][j], if dp[i-1][j] && s1[i] == s3[i+j]** 表示s1的第i个字符匹配s3的第i+j个字符；**2. dp[i][j] = dp[i][j-1], if dp[i][j-1] && s2[j] == s3[i+j]** 表示s2的第j个字符匹配s3的第i+j个字符；**上...

状态转移方程：dp[i][j] = sum(dp[i-1][0],...,dp[i-1][j-1]);还可以继续优化，可以用空间换时间，减少求解dp[i][j]的查询数量，贴出代码，请大佬给出更优的算法，以此共勉！ class Solution { public: int numDistinct(string S, string T) { int ans = 0, n = S.size(), m = T.size(); vector<vector<int> > dp(m, vector<int>(n, 0)); ...

不需要额外的空间，时间复杂度O(1/2 * N^2); class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int n = triangle.size(), ans = 0x7fffffff; if(n == 1) return triangle[0][0]; for(int i = 1; i < n; i++) { for(int j = 0; j <= i; j++)...

DP动态规划解法,时间复杂度为 O(1/4 N^3);定义：dp[i][j]表示字符串 i -> j切分成回文的答案数，状态转移方程为：dp[i][j] = min(dp[i][t]+[t+1][j]),其中t位于区间[i, j];求解过程：求解的方向，需要先求解出左下角的子三角形的解，才能求解dp[i][j],因此求解方向是按照矩形的正对角线开始，依次往右上方求解，最终dp[0][n-1]就是要求解的答案； class Solution { public: int minCut(string s) { int n = s.size(); if(i...

joshua分享：从第一个节点开始依次进行深度搜索即可，每一步的搜索都要判断是否合法，需要满足下面的几个规则：1. 当前节点没有走过；2. 当前费用足够当前节点的消费；3. 当前节点的所有前驱节点都已经走过； /** * struct Point { * int x; * int y; * }; */ class Solution { public: int Travel(int N, int V, int* A, int ALen, vector<Point>& list) { // 有N个节点，就有2^N个状态 ve...

joshua分享：首先该类问题是典型的完全背包问题，现在考虑裁剪的时候，需要考虑对现有的布料进行横向裁剪还是是竖向裁剪，每一种裁剪方法都有两种分割方法，两种裁剪方法一共有四种状态，所以每一款衣服的每一种裁剪都有四种状态选择，然后遍历所有的款式就可以了 class Solution { public: /** * * @param L int整型 给定布料的长 * @param W int整型 给定布料的宽 * @param clothSize int整型vector<vector<>> 依次列举每件衣服所需的长和宽 ...

#include<bits/stdc++.h> using namespace std; void createTree(const vector<int> &arr, int pleft, int pright, int vleft, int vright, vector<int> &ans); int main(void) { vector<int> arr; int n, t; while(cin >> t) { arr.push_back(t); } n = arr.siz...

// 遍历该层的三个节点，分别为+1， -1， *2 // 加入待选节点前，先进行判断是否合法#include <bits/stdc++.h> using namespace std; int main(void) { int level = -1, size = 0; int a, b; queue<int> q; // 这个地方为啥用cin输入就不对了？卡了我一个晚上啊！ scanf("%d,%d", &a, &b); q.push(a); while(!q.empty()) { ...

joshua分享 简单题：先打素数表，再从最小值的那个开始从最大素数开始判断 #include <bits/stdc++.h> using namespace std; int main(void) { int n, i, j, tMin = 0x7fffffff; vector<int> chart(50001, 1); vector<int> prim; cin >> n; vector<vector<int>> arr(n, vector<int>(2, 0))...