LeetCode刷题——动态规划（C/C++）

[简单]买股票的最佳时机

原题链接

• 题解
  min：今天之前买股的最低价
  res：最大利润
  每一天比较今天和往前的最低价差值能否比最大利润还大

class Solution {
public:int maxProfit(vector<int>& prices) {int min = INT_MAX;int res = 0;for (int i = 0; i < prices.size(); i++) {if (prices[i] < min) {min = prices[i];}if ((prices[i] - min )> res) {res = prices[i] - min;}}return res;}
};

[简单]爬楼梯

原题链接

• 题解
  走到第n阶的方法数其实就正好包括
  （1）走到第n-1阶之后再走一阶
  （2）走到第n-2阶之后再走两阶。
  注意：走到第n-2阶之后只能算上再走两阶的方案，因为如果加上再走两次一阶，就会和（1）里面的方案重复

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

[中等]最长递增子序列

原题链接

• 题解
  用f[i]来表示以i为结尾的最大递增子序列长度，先给定所有单个数字最长字段各自为1，即f[i]=1（即只包括自己）
  然后从左往右遍历， 每遍历到i，都嵌套遍历一次i之前所有的数nums[j]是否小于nums[i]，如果是的话，就有了一段基于f[j]+1长度的递增子序列，进而找出以i为末尾的最长递增子序列

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int f[2550];for (int i = 0; i < nums.size(); i++) {f[i] = 1;}for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && (f[j] + 1)> f[i])f[i] = f[j] + 1;}}int max = 1;for(int i=0;i<nums.size();i++){if(f[i]>max) max=f[i];}return max;}
};

[中等]最大连续子数组和

原题链接

• 题解

class Solution {
public:int maxSubArray(vector<int>& nums) {int f[100010];f[0] = nums[0];for(int i=1;i<nums.size();i++){f[i]= max(nums[i],f[i-1]+nums[i]);}int max = f[0];for(int i=1;i<nums.size();i++){if (f[i]>max) max = f[i];}return max;}
};