day43

今天完成了三道动规的子序列题，有点难度。
最长递增子序列：
//dp[i]：下标为i时的最长递增子序列的长度
        //递推公式：
        //if(nums[i] > nums[j]) dp[i] = max(dp[j] + 1, dp[i]);
        //初始化：全初始化为1
        //遍历顺序，两层for循环，外层i，内层j（j < i）

        if(nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 1);
        int result = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[j] + 1, dp[i]);
                }
            }
            result = max(result, dp[i]);
        }
        return result;//不一定是以最后一个元素为结尾时是最长子序列

最长连续递增子序列：简单

两个数组间的最长重复数组：
//dp[i][j]：以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度
        //注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 
        //递推公式：
        //if(nums[i] == nums[j]) dp[i][j] = dp[i-1][j-1] + 1;
        //初始化，全初始化为0，因为dp[i][0],dp[0][j]其实没有意义，而其他的则会被覆盖
        //遍历顺序：两层for循环
        if(nums1.size() == 0 || nums2.size() == 0) return 0;
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for(int i = 1; i <= nums1.size(); i++)
        {
            for(int j = 1; j <= nums2.size(); j++)
            {
                if(nums1[i-1] == nums2[j-1])//是i-1，j-1时的元素相等
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                result = max(dp[i][j], result);//持续记录最大值
            }
        }
        return result;

这几天终于把Reactor框架学完了！