二刷list2019年03月31日
151. Best Time to Buy and Sell Stock III
int maxProfit(vector<int> &prices) { // write your code here // DP //好吧，还是要整理DP思路先。 //状态 f[i][j] 前i-th element 最多交易j次的收益。 //转移：在第i-th 元素看，分情况： //1, day i 没有交易: f[i][j] = f[i - 1][j]. //2, day i 有交易。1) 第i - 1天没有卖: f[i][j] = f[i - 1][j - 1] + max(0, prices[i- 1] - prices[i - 2); // 2) 第i - 1天卖了: f[i][j] = p[i - 1][j] + diff; //需要第二个状态: 表示在第i天卖了这个特定条件下，最多交易j次的收益p[i][j],实际上就是上面f[i][j]里的case2. // 站在第i天，第i天卖了：p[i][j] = max(f[i - 1][j - 1] + max(0, prices[i - 1] - prices[i - 2]), p[i-1][j] + diff; //iniial, 都是0. const int n = prices.size(); if(n == 0){ return 0; } //vector<vector<int>> f(n + 1, vector<int>(3, 0)); //vector<vector<int>> p(n + 1, vector<int>(3, 0)); vector<int> f(3, 0); vector<int> p(3, 0); for(int i = 2; i < n + 1; i++){ for(int j = 2; j >= 1; j--){ //这里有一个技巧，j是从大往小更新。这是因为，参照二维的形式。 //p[i][j] = max(f[i - 1][j - 1] + max(0, diff), p[i - 1][j] + diff); // f[i][j] = max(p[i][j], f[i - 1][j]); 每次更新用的都是 index i -1里的值，也就是上一轮的值。所以要从后往前的更新，否则，如果从前往后，i + 1要用i, 但i在更新时，已经被重写，不再是上一轮里的 index i 对应的值。 int diff = prices[i - 1] - prices[i - 2]; p[j] = max(f[j - 1] + max(0, diff), p[j] + diff); f[j] = max(p[j], f[j]); //之和前一个 i - 1有关系，所以可以i维度用一个量表示节省空间 } } return f[2]; }
int maxProfit(vector<int> &prices) { // write your code here // DP //好吧，还是要整理DP思路先。 //状态 f[i][j] 前i-th element 最多交易j次的收益。 //转移：在第i-th 元素看，分情况： //1, day i 没有交易: f[i][j] = f[i - 1][j]. //2, day i 有交易。1) 第i - 1天没有卖: f[i][j] = f[i - 1][j - 1] + max(0, prices[i- 1] - prices[i - 2); // 2) 第i - 1天卖了: f[i][j] = p[i - 1][j] + diff; //需要第二个状态: 表示在第i天卖了这个特定条件下，最多交易j次的收益p[i][j],实际上就是上面f[i][j]里的case2. // 站在第i天，第i天卖了：p[i][j] = max(f[i - 1][j - 1] + max(0, prices[i - 1] - prices[i - 2]), p[i-1][j] + diff; //iniial, 都是0. const int n = prices.size(); if(n == 0){ return 0; } //vector<vector<int>> f(n + 1, vector<int>(3, 0)); //vector<vector<int>> p(n + 1, vector<int>(3, 0)); vector<int> f(3, 0); vector<int> p(3, 0); for(int i = 2; i < n + 1; i++){ for(int j = 2; j >= 1; j--){ //这里有一个技巧，j是从大往小更新。这是因为，参照二维的形式。 //p[i][j] = max(f[i - 1][j - 1] + max(0, diff), p[i - 1][j] + diff); // f[i][j] = max(p[i][j], f[i - 1][j]); 每次更新用的都是 index i -1里的值，也就是上一轮的值。所以要从后往前的更新，否则，如果从前往后，i + 1要用i, 但i在更新时，已经被重写，不再是上一轮里的 index i 对应的值。 int diff = prices[i - 1] - prices[i - 2]; p[j] = max(f[j - 1] + max(0, diff), p[j] + diff); f[j] = max(p[j], f[j]); //之和前一个 i - 1有关系，所以可以i维度用一个量表示节省空间 } } return f[2]; }
28. Search a 2D Matrix
88. Lowest Common Ancestor of a Binary Tree
393. Best Time to Buy and Sell Stock IV
412. Candy
Comments
Post a Comment