状态转移方程为： 当s1[i] = s2[j]时: 当s1[i] != s2[j]时: // runtime: 4ms // space: 504K // complexity: O(m*n) #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAX = 1001; string s1; string s2; //int dp[MAX][MAX]; // 也可以使用全局二维数组，并且自动初始化为所有元素都是0...

两次DP求最长递增子序列，然后，结果是 // runtime: 3ms // space: 496K #include <iostream> #include <algorithm> using namespace std; const int MAX = 100; int arr1[MAX]; int arr2[MAX]; // reversal of arr1 int dp1[MAX]; // arr1 max increase subsequence int dp2[MAX]; // arr2 max increase subsequence voi...

DP问题

最长递增子序列的变形问题。 // runtime: 4ms // space; 496K #include <iostream> #include <cstdio> using namespace std; const int MAX = 1000; int arr[MAX]; int dp[MAX]; // 以arr[i]为结尾的最大上升子序列和 int MaxIncSubsequence(int k) { int sum = 0; for (int i = 0; i < k; ++i) { dp[i] = arr[i]; ...

// runtime: 4ms // space: 504K #include <iostream> #include <cstdio> using namespace std; const int MAX = 25; int arr[MAX]; int dp[MAX]; // dp[i]定义为：以arr[i]为结尾的最长递增(减)子序列。 int MaxDecSubsequence(int k) { int answer = 0; for (int i = 0; i < k; ++i) { dp[i] = 1; ...

本题考察的是二叉树的建立，并且输出父节点的值。所以函数Insert的参数里多了一个int型的变量father，记录的是父节点的值。因为二叉排序树的新增节点都是在叶子处，所以root == NULL时，新建一个结点BTree(x)。 // runtime: 5ms // space: 504K #include <iostream> using namespace std; struct BTree { int data; BTree* leftChild; BTree* rightChild; BTree(int x) : data(x), lef...

此题考察最基本的二叉树的构造和中序遍历。 // runtime: 3ms // space: 488K #include <iostream> #include <string> using namespace std; // 二叉树结构体 struct BTree { char data; BTree* leftChild; BTree* rightChild; BTree(char c) : data(c), leftChild(NULL), rightChild(NULL) {} }; // 构造二叉树 BTree* BuildTr...

问：为啥今天没刷题？答：太菜了，刷不动啊。看啥啥不会，让学还不学。

一道题整一天

贪心算法完结

此题的题意是给定一个数n，先分解成二进制和的形势2的i次方的和 。比如： ，而系数 ，直到2上面的系数i全为0或者1为止。2直接输出为2， 输出为2(0),所以输入为9，输出为2(2+2(0))+2(0),即 。 所以此题非常适合使用递归策略。 // runtime: 4ms // space: 488K #include <iostream> #include <vector> using namespace std; // 计算base的n次方。 int MyPow(int base, int n) { int result = 1; for (i...

分治：即把一个复杂的问题分成两个或多个子问题，子问题之间相互独立且与原问题相同或相似，持续分解，直到最后的子问题可以简单的求解。原问题即子问题解的合并。 由于反复利用分治手段，这就为使用递归策略提供了条件。 解法：采用递归策略，根据二叉树的性质：左子树编号为2m,右子树为2m+1，不断的去计算节点数。 #include <iostream> using namespace std; int BinaryTree(int m, int n) { if(m <= n) { return 1 + BinaryTree(m * 2, n) + Binar...