ls.joshua

分类

题解(10)

/ 注册

全部文章（共9篇）

joshua分享：dp[i][j]定义：用s1[1...i],s2[1...j] 能否匹配 s3[1...i+j]

这道题比较简单，一开始写的递归，后来改成循环，发现都超时。写了一个简易版本的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] &&a...

2020-04-21

0 816

joshua分享：动态规划解法，入门级别解法

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

2020-04-21

0 837

joshua分享：直接自顶向下计算，计算完后最后一行的数据筛选出的最小值就是答案

不需要额外的空间，时间复杂度O(1/2 * N^2); class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int n = triangle.s...

2020-04-21

0 1053

joshua分享：DP动态规划解法,时间复杂度为 O(1/4*N^3);

DP动态规划解法,时间复杂度为 O(1/4 N^3);定义：dp[i][j]表示字符串 i -> j切分成回文的答案数，状态转移方程为：dp[i][j] = min(dp[i][t]+[t+1][j]),其中t位于区间[i, j];求解过程：求解的方向，需要先求解出左下角的子三角形的解，才能求...

2020-04-20

1 1182

joshua分享：从第一个节点开始依次进行深度搜索即可，每一步的搜索需要如下满足三个条件！

joshua分享：从第一个节点开始依次进行深度搜索即可，每一步的搜索都要判断是否合法，需要满足下面的几个规则：1. 当前节点没有走过；2. 当前费用足够当前节点的消费；3. 当前节点的所有前驱节点都已经走过； /** * struct Point { * int x; * int y; ...

2020-04-08

0 959

joshua分享：dp[i][j] 表示裁剪长度为i,宽度为j的布料最大所裁剪的衣服数量

joshua分享：首先该类问题是典型的完全背包问题，现在考虑裁剪的时候，需要考虑对现有的布料进行横向裁剪还是是竖向裁剪，每一种裁剪方法都有两种分割方法，两种裁剪方法一共有四种状态，所以每一款衣服的每一种裁剪都有四种状态选择，然后遍历所有的款式就可以了 class Solution { public:...

2020-04-07

0 1007

感觉前序和中序遍历这颗二叉树，但是不需要建树，直接对节点求和就可以了！

#include<bits/stdc++.h> using namespace std; void createTree(const vector<int> &arr, int pleft, int pright, int vleft, int vright, ve...

2020-04-04

3 1081

joshua分享：用队列实现，相当于是BFS搜索，只有三条分支路。

// 遍历该层的三个节点，分别为+1， -1， *2 // 加入待选节点前，先进行判断是否合法#include <bits/stdc++.h> using namespace std; int main(void) { int level = -1, size = 0;...

2020-03-25

2 989

joshua分享简单题：先打素数表，再从最小值的那个开始从最大素数开始判断

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

2020-03-25

0 867