前言：本文为学习力扣文章《动态规划精讲（一）》时的学习笔记，本文对其进行线性动态规划相关的文章和问题进行了一定的转载和修改并在其中加入了一些个人的理解。

线性动态规划简介

线性动态规划主要是从0开始从小到大依次递推过去的，特点为问题规模依次从0到i依次递增，较大规模的问题依赖较小规模问题的解

这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

状态定义：

1

dp[n] := [0..n] 上问题的解

状态转移：

1

dp[n] = f(dp[n-1], ..., dp[0])

单串

单串是线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0...i]上，原问题的解，其中 i 位置的处理，根据不同的问题，主要有两种方式：

• 第一种是 i 位置必须取，此时状态可以进一步描述为 dp[i] := 考虑[0...i]上，且取 i，原问题的解；
• 第二种是 i 位置可以取可以不取

剑指 Offer 25. 合并两个排序的链表

难度 简单

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

1
2

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

1

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

剑指 Offer 22. 链表中倒数第k个节点

难度 简单

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1
2
3

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

剑指 Offer 48. 最长不含重复字符的子字符串

难度 中等

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

1
2
3

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

剑指 Offer 42. 连续子数组的最大和

难度 简单

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

1
2
3

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/