打家劫舍系列

198. 打家劫舍对于当前的房间，无非就两种选择：偷与不偷。如果当前房间偷，那么前一个房间就不偷，即dp[i] = dp[i-2] + nums[i]；如果当前房间不偷，那么dp[i] = dp[i-1]，因此递推公式为：

10余年的蟠龙网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。营销型网站建设的优势是能够根据用户设备显示端的尺寸不同，自动调整蟠龙建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联从事“蟠龙网站设计”,“蟠龙网站推广”以来，每个客户项目都认真落实执行。

dp[i] = max(dp[i-1],dp[i-2] + nums[i])

213. 打家劫舍 II这个题上上一题的基础之上加入了成环的约束条件，因为第一间房间和最后一间房间只能偷一间，因此可以分为两种情况，一种是不偷第一间房，另一种是不偷最后一间房间，这样两种情况都不同考虑成环的问题且都转化为了上一个题，因此可以用上一个题的思路求解，最终的结果是两种情况中的大值。
337. 打家劫舍 III这题将数组变成了树，因此涉及到树的遍历方式，这里使用后序遍历。

买卖股票系列

121. 买卖股票的最佳时机这个题只能买卖一次，因此只能在最低点买入，在最低点后的最高点卖出，定义dp数组dp[i][0]和dp[i][1]，递推公式如下：

dp[i][0] = min(prices[i],dp[i-1][0]);				//买入时花费的最少现金
dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0]);		//卖出时所得的大利润

122. 买卖股票的最佳时机 II这个题可以多次买卖，因此在买入的时候还要考虑在此之前花费的现金，递推公式如下，注意和上一个题递推公式的差别：

dp[i][0] = min(prices[i] - dp[i-1][1],dp[i-1][0]);  	//买入时花费的最少现金
dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0]);			//卖出时所得的大利润

123. 买卖股票的最佳时机 III和188. 买卖股票的最佳时机 IV求解思路是一样的，在只允许买卖两次的时候就可以发现规律，无非就是要列出每天的所有可能状态。买卖k次时的代码实现如下：

class Solution {public:
    int maxProfit(int k, vector& prices) {vector>dp(prices.size(),vector(2 * k + 1));
        //初始化dp数组
        for(int j = 1 ; j< 2 * k + 1; j += 2) //注意这里是j += 2
            dp[0][j] = -prices[0];  //买入状态初始化，卖出状态已经初始化为0
        //遍历
        for(int i = 1; i< dp.size(); i++){//dp[i][0] = dp[i-1][0];  //始终保持不变，可以不用
            for(int j = 1; j< 2 * k + 1; j += 2){  //注意这里是j += 2
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i]);    //买入
                dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j] + prices[i]);  //卖出
            }
        }
        return dp.back()[2*k];
    }
};

当j为奇数的时候表示买入，当j为偶数的时候表示卖出。

309. 最佳买卖股票时机含冷冻期这个题在前四个题的基础上加入了冷冻期，在求解过程中要理清楚状态转移过程，在这个题中定义下面的四个状态：

• 状态一（ j = 0）：买入状态，不一定当天买入，也可能是之前就已经买入了
• 状态二（ j = 1）：卖出状态且已经度过了冷冻期
• 状态三（ j = 2）：今天卖出，还未度过冷冻期
• 状态四（j = 3）：冷冻期

根据状态转移关系即可得到递推公式：

dp[i][0] = max(dp[i-1][0],max(dp[i-1][1] - prices[i],dp[i-1][3] - prices[i]));
dp[i][1] = max(dp[i-1][1],dp[i-1][3]);
dp[i][2] = dp[i-1][0] + prices[i];
dp[i][3] = dp[i-1][2];

714. 买卖股票的最佳时机含手续费这个题在122. 买卖股票的最佳时机 II的基础上加入了手续费，因此在卖出的时候考虑手续费即可。

子序列问题

子序列问题一定要清楚dp[i]的定义，以及子序列连续和不连续的求解区别。

300. 最长递增子序列中dp[i]定义为以nums[i]作为子序列的最后一个元素的最长子序列为dp[i]，因此最终的结果是dp数组中的大值。核心代码如下：

for(int i = 1; i< nums.size(); i++){for(int j = 0; j< i; j++){if(nums[i] >nums[j]) dp[i] = max(dp[i],dp[j]+1);
    }
    if(dp[i] >result)  result = dp[i];
}

674. 最长连续递增序列这个题要求子序列是连续的，因此dp[i]只能和dp[i-1]有关系，递推公式为：

if(nums[i] >nums[i-1]) dp[i] = dp[i-1] + 1;

如果不满足nums[i] >nums[i-1]，则dp[i]保持1不变（初始化的时候已经赋值为1），因此一个元素就可以构成一个子序列。

718. 最长重复子数组这个题涉及到两个数组，因此要使用二维dp数组，且dp[i][j]只能由dp[i-1][j-]1得到。如下图所示：

1143. 最长公共子序列和718. 最长重复子数组的区别在于这题的子序列不连续，差异主要体现在初始化和递推公式上，本题的递推公式为：

if(text1[i] == text2[j])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

dp[i][j]不仅和dp[i-1][j-1]有关，还和dp[i-1][j]、dp[i][j-1]有关。

1035. 不相交的线和1143. 最长公共子序列完全一样，关键是要想明白怎么个一样法！

53. 大子序和这个题其实就是求的是局部的大和，dp数组中保存的是局部大和，最终的结果是dp数组中的大值，递推公式如下：

dp[i] = max(dp[i-1] + nums[i],nums[i]);

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：代码随想录训练营第54天|休息日小结-创新互联
路径分享：http://kswjz.com/article/dsihho.html