动态规划学习笔记（待更新...)

（无模板）

背包问题

1. 01 01 01背包：每件物品最多用一次

2.完全背包：每件物品有无限个

3.多重背包：每种物品个数不一样，有限制（可优化）

4.分组背包： n n n组物品，每组物品最多只能选一种物品

例题： 01 01 01背包

优化前：

#include 
#include 
using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];//状态集合，初始值都为0

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
    for(int i=1;i<=n;i++)/
 
啥也没说，思路有点混了。。。
 
区间
     
      
       
        
         D
        
        
         P
        
       
       
        DP
       
      
     DP
 
例题：石子合并
 
#include 
using namespace std;

const int N = 310;
int n;
int s[N],f[N][N];

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<=n;i++) s[i]+=s[i-1];//求前缀和
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int l=i,r=i+len-1;  //区间范围
            f[l][r]=1e9;        //*初始化后续做比较取最小
            for(int k=l;k 
坑：
    
     
      
       
        f
       
       
        o
       
       
        r
       
       
        (
       
       
        i
       
       
        n
       
       
        t
       
       
         
       
       
        l
       
       
        e
       
       
        n
       
       
        =
       
       
        2
       
       
        ;
       
       
        l
       
       
        e
       
       
        n
       
       
        ≤
       
       
        n
       
       
        ;
       
       
        l
       
       
        e
       
       
        n
       
       
        +
       
       
        +
       
       
        )
       
      
      
       for(int len=2;lenle n;len++)
      
     
    for(int len=2;len≤n;len++) 竟然长度是从
    
     
      
       
        2
       
      
      
       2
      
     
    2枚举到
    
     
      
       
        n
       
       
        ?
       
       
        ?
       
      
      
       n??
      
     
    n??
 
不能理解。。。到
    
     
      
       
        n
       
       
        −
       
       
        1
       
      
      
       n-1
      
     
    n−1输出一直为
    
     
      
       
        0
       
      
      
       0
      
     
    0…
 
好像知道了，下一步循环要用到
    
     
      
       
        l
       
       
        e
       
       
        n
       
      
      
       len
      
     
    len, 
    
     
      
       
        l
       
       
        e
       
       
        n
       
      
      
       len
      
     
    len到
    
     
      
       
        n
       
      
      
       n
      
     
    n后面求右边界才能到达
    
     
      
       
        n
       
      
      
       n
      
     
    n的位置。