376.摆动序列

感觉没什么，就是检测拐点

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {//0 is equal, //1 is up,//2 is down//-1 is uninializeint is_up = -1;vector<int> reslut;if(nums.size() < 1){return nums.size();}int fisrt = nums.at(0);for(int i=0; i<nums.size(); i++){int current = nums.at(i);int next;if(i + 1 < nums.size()){next = nums.at(i+1);}else{break;}if(is_up == -1){if(next > current){is_up = 1;reslut.push_back(fisrt);}if(next < current){is_up = 2;reslut.push_back(fisrt);}}if(is_up == 1){if(next >= current){continue;}else{reslut.push_back(current);is_up = 2;}}if(is_up == 2){if(next > current){reslut.push_back(current);is_up = 1;}else{continue;}}}int last_value = nums.at(nums.size() - 1);reslut.push_back(last_value);return reslut.size();}
};

509. 斐波那契数

效率不是很高

class Solution {
public:int fib(int n) {if(n <= 0){return 0;}if(n == 1){return 1;}if(n > 1){return fib(n-1) + fib(n-2);}return 0;}
};

70.爬楼梯

使用递归比较耗时，能不用尽量不用，虽然比较好理解

class Solution {private:int dp[50];public:int climbStairs(int n) {dp[1]=1;dp[2]=2;for(int i=3; i<=n; i++){dp[i]=dp[i-1] + dp[i-2];}return dp[n];}
};

746.使用最小花费爬楼梯

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int count = cost.size() - 1;int bt_cost[1000];bt_cost[0] = cost.at(0);if(count < 1){return cost.at(0);}bt_cost[1] = std::min(bt_cost[0], cost.at(1));if(count < 2){return bt_cost[count];}bt_cost[2] = std::min(bt_cost[0]+cost.at(2), cost.at(1));for(int i=3; i<cost.size(); i++){bt_cost[i] = std::min(bt_cost[i-1] + cost.at(i),bt_cost[i-2] + cost.at(i-1));}return bt_cost[count];}
};

62.不同路径

class Solution {
public:int uniquePaths(int m, int n) {int data[m][n];for(int i=0; i<m;i++){for(int j=0; j<n; j++){if(i == 0 || j == 0){data[i][j] = 1;continue;}data[i][j] = data[i-1][j] + data[i][j-1];}}return data[m-1][n-1];}
};

63.不同路径2

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid.at(0).size();int data[m][n];if(obstacleGrid.at(0).at(0) == 1){data[0][0] = 0;}else{data[0][0] = 1;}for(int i=0; i<m;i++){for(int j=0; j<n; j++){if(obstacleGrid.at(i).at(j) == 1){data[i][j] = 0;continue;}int part_1 = 0;if(i-1 >= 0){part_1 = data[i-1][j];}int part_2 = 0;if(j-1 >=0){part_2 = data[i][j-1];}if(i==0 && j==0){continue;}else{data[i][j] = part_1 + part_2;}}}return data[m-1][n-1];}
};

343.整数拆分

class Solution {
public:int integerBreak(int n) {if(n==1){return 0;}if(n==2){return 1;}if(n==3){return 2;}//elseint result[n+1];result[1] = 0;result[2] = 2;result[3] = 3;result[4] = 4;for(int i=5; i<=n; i++){int time = n/3;int last = n%3;if(last == 1){time--;last += 3;}result[i] = 1;while(time > 0){result[i] *= 3;time--;}if(last == 0){return result[i];}else{result[i] *= result[last];}}return result[n];}
};

96.不同的二叉搜索树

class Solution {
public:int numTrees(int n) {if(n==1){return 1;}int tree_num[n+1];tree_num[0] = 1;tree_num[1] = 1;tree_num[2] = 2;for(int i=3; i<=n; i++){tree_num[i] = 0;for(int j=1; j<=i; j++){int left = j-1;int right = i-j;tree_num[i] += (tree_num[left]*tree_num[right]);}}return tree_num[n];}
};