【线性动态规划】线性动态规划与单串问题

• 线性动态规划：
  
  • 按照问题的规模i从小到大依次推过去，较大规模问题的解依赖于较小规模问题的解
    
    • 
      
  • 线性动态规划解决的问题：单串dp[i]、带维度单串dp[i][k]、双串和矩阵
    
  • 单串相关问题
    
    • 最简单的一类DP，输入是一个串(or数组)，状态一般定义为dp[i]:=[0…i]上原问题的解
      
    • LIS
      
      • 最长上升子序列
        
      • 最长上升子序列的个数（统计个数dp）
        
      • 俄罗斯套娃信封问题（lambda表达式）
        
    • 最大子数组和
      
      • 最大子序和
        
      • 乘积最大子数组（分组dp）
        
      • 环形子数组最大和(Kadane算法)
        
    • 打家劫舍
      
    • 带维度单穿dp[i][k]
      
    • 股票