求解爬楼梯问题（每次可爬1级或2级台阶，求到达第n级台阶的总走法数）的状态转移方程可写为dp[i] = dp[i-1] + dp[i-2]，初始条件设为dp[0]=0、dp[1]=1，该问题的空间复杂度最优可降到O(1)

求解长度为n的数组的最大子数组和问题，线性DP的状态可定义为dp[i]表示以第i个元素结尾的最大子数组和，状态转移方程为dp[i] = max(dp[i-1] + nums[i], nums[i])，该解法时间复杂度为O(n)

求解最长上升子序列（LIS）的纯线性DP解法时间复杂度为O(n)，状态转移方程为dp[i] = max{ dp[j] + 1 | 0 ≤ j < i 且 nums[j] < nums[i] }

线性动态规划的所有问题都必须按照从左到右的顺序递推状态，不能采用反向递推的方式设计解法