动态规划：本周我们都讲了这些（系列八）

本周我们结束了股票系列的最后一道题目，然后开始了子序列系列，这个系列和背包系列一样，都是动规解决的经典问题。

周一

动态规划：买卖股票的最佳时机含手续费中是每笔交易都有手续费了。

相对于动态规划：122.买卖股票的最佳时机II，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。

递归公式：

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

本题和动态规划：122.买卖股票的最佳时机II的区别就是第二个公式需要多一个减去手续费的操作。

周二

周二开始讲解子序列问题，先来一道入门题目

动态规划：最长递增子序列寻找最长递增子序列的长度。

1. dp[i]的定义

dp[i]表示i之前包括i的最长上升子序列。

1. 状态转移方程

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

1. dp[i]的初始化

每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是是1.

1. 确定遍历顺序

dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：

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]; // 取长的子序列
}

1. 举例推导dp数组

输入：[0,1,0,3,2]，dp数组的变化如下：

本题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);

子序列问题是动态规划的一个重要系列，本题算是入门题目，好戏刚刚开始！

周三

动态规划：最长连续递增序列这次要求连续递增子序列的长度了，注意是**“连续”**

1. 确定dp数组（dp table）以及下标的含义

dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。

1. 确定递推公式

dp[i + 1] = dp[i] + 1;

注意这里就体现出和动态规划：300.最长递增子序列的区别！

因为本题要求连续递增子序列，所以就必要比较nums[i + 1]与nums[i]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。

1. dp数组如何初始化

以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。

所以dp[i]应该初始1;

1. 确定遍历顺序

从递推公式上可以看出， dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。

for (int i = 0; i < nums.size() - 1; i++) {
    if (nums[i + 1] > nums[i]) { // 连续记录
        dp[i + 1] = dp[i] + 1; // 递推公式
    }
}

1. 举例推导dp数组

已输入nums = [1,3,5,4,7]为例，dp数组状态如下：

注意这里要取dp[i]里的最大值，所以dp[2]才是结果！

在动规分析中，关键是要理解和动态规划：300.最长递增子序列的区别。

要联动起来，才能理解递增子序列怎么求，递增连续子序列又要怎么求。

概括来说：不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关

周四

二维数组的地址分布究竟是什么样的？在数组专题的文章讲解中，讲到了二维数组的地址分布情况。

当时讲的时候并没有说明区间语言上的差别，事实上C++的二维数组在内存地址上是连续的，而Java不是连续的。

最近抽空做了实验也证实了这一点，所以单独发文讲解一下。

C++中二维数组的内存分布，如图：

Java中的二维数据的内存分布，如图：