精华内容
下载资源
问答
  • 区间dp

    2019-09-27 14:22:17
    区间dp就是在区间上的动态规划,求解一段区间上的最优解,通过合并小区间的最优解来得到整个大区间上的最优解的算法。 区间dp一般都是三层for循环 需要注意的是 区间是从小到大 因为dp是后一个用到前一个的给出的...
    区间dp就是在区间上的动态规划,求解一段区间上的最优解,通过合并小区间的最优解来得到整个大区间上的最优解的算法。
    区间dp一般都是三层for循环 需要注意的是 区间是从小到大 因为dp是后一个用到前一个的给出的结果 并进行递推 
    区间dp常用的一个状态就是dp[i][j]表示i~j这个区间的最优解多少
    区间dp的大致思路:
      1.确定状态 初始化长度为 n 的dp[][]的值
      2.枚举区间长度 枚举区间的起始点 (有些题还需枚举断点) 由小区间转移到大区间
      3.最终答案基本是 dp[1][n] or dp[0][n-1]

     

    区间dp 模板
     1 //memset(dp,0,sizeof(dp)) 初始化DP数组
     2 for(int i=1;i<=n;i++){
     3     dp[i][i]=初始值
     4 }
     5 for(int len=2;len<=n;len++)  //区间长度
     6 for(int i=1;i<=n;i++){       //枚举区间起点
     7     int j=i+len-1;           //区间终点
     8     if(j>n) break;           //越界结束
     9     for(int k=i;k<j;k++){     //枚举分割点,构造状态转移方程
    10         dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
    11     }
    12 }

     



     

    升级

    1.由直线型变换成环形
      若是环形,则需要将整个数组复制一遍,然后在统计答案的时候,把1-n开头长度为n的区间求一个min 即可

    2.优化 —— 四边形不等式优化

    https://blog.csdn.net/noiau/article/details/72514812
    //大佬blog 侵删


     

    题目

    1.石子合并

    2.Pangu and stone
     1 #include<iostream>
     2 #include<cstring>
     3 
     4 using namespace std;
     5 const int inf=0x3f3f3f3f;
     6 int n,l,r,a[105],sum[105],dp[105][105][105];
     7 
     8 void f(){
     9     for(int d=1;d<=n;d++){            //区间长度 
    10         for(int i=1;i+d-1<=n;i++){            //区间起点 
    11             int j=i+d-1;                    //区间终点 
    12             for(int k=i;k<j;k++){            //在区间内枚举 
    13                 for(int s=l;s<=r;s++){            //一次 可 合并 区间 数 
    14                     dp[i][j][1]=min(dp[i][j][1],dp[i][k][s-1]+dp[k+1][j][1]+sum[j]-sum[i-1]);
    15                 }
    16             }
    17             for(int k=2;k<=n;k++){
    18                 for(int s=i;s<j;s++){            //枚举分割点 构造状态转移方程 
    19                     dp[i][j][k]=min(dp[i][j][k],dp[i][s][k-1]+dp[s+1][j][1]);
    20                 }
    21             }
    22         }
    23     } 
    24     if(dp[1][n][1]==inf)cout<<0<<endl;
    25     else cout<<dp[1][n][1]<<endl;    
    26 } 
    27 
    28 int main(){
    29     while(cin>>n>>l>>r){
    30         for(int i=1;i<=n;i++){
    31             cin>>a[i];
    32             sum[i]=sum[i-1]+a[i];
    33         }
    34         memset(dp,inf,sizeof(dp));
    35         for(int i=1;i<=n;i++){
    36             for(int j=i;j<=n;j++)
    37                 dp[i][j][j-i+1]=0;
    38         }
    39         f();
    40     }
    41     return 0;
    42 }
    View Code

     







     

    转载于:https://www.cnblogs.com/jjjjjjy/p/11367525.html

    展开全文
  • 区间DP

    2020-07-31 02:12:38
    区间DP一般需要从小到大枚举所有可能的区间,先解决小区间问题然后合并小区间得到更大的区间,直到解决最后的大区间问题。合并的一般操作是把左右两个相邻的子区间合并。区间DP大概就难在这了吧:枚举所有可能的区间...

    定义

      就是求一个区间内的最优解咯(日常解释了个寂寞,相信大家都能看懂的哈)

    核心思想

      先在小区间进行DP得到最优解,然后再利用小区间的最优解合并求大区间的最优解。等于没说,,,这个思想谁都会,其实就难在到底怎么合并,铠甲勇士合体吗。区间DP一般需要从小到大枚举所有可能的区间,先解决小区间问题然后合并小区间得到更大的区间,直到解决最后的大区间问题。合并的一般操作是把左右两个相邻的子区间合并。区间DP大概就难在这了吧:枚举所有可能的区间、状态转移方程。

    复杂度

      区间DP至少需要两层for循环,第1层的i从区间的首部或尾部开始,第2层的ji开始到结束,ij一起枚举出所有的子区间。

    for(int i=1; i<n; i++)		//n是区间长度
    	for(int j=i; j<=n; j++)	//
    

    经典例题

    1.石子合并

      有n堆石子排成一排,每堆石子有一定的数量,请将n堆石子合并成一堆。合并的规则则是每次只能合并相邻的两堆石子,合并的花费为这两堆石子的总数。石子经过n-1次合并后成为一堆,求总的最小花费。
      输入:有多组测试数据,输入到文件结束。每组测试数据的第1行有一个整数n,表示有n堆石子,n<250。接下来的一行有n个数,分别表示这n堆石子的数目。每堆石子至少1颗,最多10000颗。
      输入样例:
      3
      2 4 5
      输出样例:
      17

      样例的计算过程:(1)第一次合并2+4=6(2)第二次合并6+5=11。总花费是6+11=17。
      定义状态dp[i][j]表示从第 i 堆石子到第 j 堆石子的最小花费,那么dp[1][n]就是答案。另外需要定义sum[i][j]表示从第 i 到 j 的区间的和。合并过程:
      (1)合并之前,dp数组初始化为0。
      (2)两堆合并:dp[i][i+1] = dp[i][i]+dp[i+1][i+1]+sum[1][2];
      (3)三堆合并:dp[i][i+2] = min(dp[i][i]+dp[i+1][i+2], dp[i][i+1]+dp[i+2][i+2]) + sum[i][i+2];
      (4)总结:第 i 堆到第 j 堆的合并即 状态转移方程

    dp[i][j] = min(dp[i][k]+dp[k+1][j]) + sum[i][j-i+1];//i ≤ k ≤ j
    

      然后就是全部代码了,结合上面的似有似无的解释,应该能看得懂了。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int inf = 1 << 30;
    const int N = 300;
    
    int n, x, sum[N];
    int DP(){
        int dp[N][N];
        for (int i = 1; i <= n; i++)
            dp[i][i] = 0;
        for (int len = 1; len < n; len++)			//len 为区间长度-1
            for (int i = 1; i + len <= n; i++){		//从第i堆开始
                int j = i + len;					//到第j堆结束
                dp[i][j] = inf;
                for (int k = i; k < j; k++)			//区间内用k进行分割
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        return dp[1][n];
    }
    
    int main(){
        while(cin >> n){
            sum[0] = 0;
            for (int i = 1; i <= n; i++){
                cin >> x;
                sum[i] = sum[i - 1] + x;
            }
            cout << DP() << endl;
        }
        return 0;
    }
    

      emmmm这个DP函数是可以优化的,但是这个优化的 “平行四边形优化原理” 我还不太懂哈,所以这里就不写了。

    2.环形石子合并

    传送门

    3.回文串

    传送门
    偷了个懒,因为之前已经写过这两个题了,然后又刚好是经典题型,就直接扔链接了哈。

    展开全文
  • 区间 DP

    2020-11-02 11:13:58
    主要思想:先在小区间进行 DP 得到最优解,然后再利用小区间的最优解合并求大区间的最优解 区间 DP,一般需要从小到大枚举所有可能的区间。在解题时,先解决小区间问题,然后合并小区间,得到更大区间,直到解决...

    概念

    主要思想:先在小区间进行 DP 得到最优解,然后再利用小区间的最优解合并求大区间的最优解

    区间 DP,一般需要从小到大枚举所有可能的区间。在解题时,先解决小区间问题,然后合并小区间,得到更大区间,直到解决最后的大区间问题。合并的操作一般是把左、右两个相邻的子区间合并

    两个难点:枚举所有可能的区间、状态转移方程

    复杂度:一个长度为 n 的区间,它的子区间数量级为 O(n^2),每个子区间内部处理时间不确定,合起来复杂度会大于 O(n^2)。

    在编程时,区间 DP 至少需要两层 for 循环,第 1 层的 i 从区间的首部或尾部开始,第 2 层的 j 从 i 开始到结束,i 和 j 一起枚举出所有的子区间。例如:

     1、石子合并

    问题描述

     解题思路

    样例的计算过程是:(1)第一次合并:2+4=6;(2)第二次合并:6+5=11;总花费是:6+11=17

    DP 的状态如何设计?设 dp[i][j] 为从第 i 堆石子到第 j 堆石子的最小花费,那么 dp[1][n] 就是答案。另外,设 sum[i][j] 为从第 i 到 j 的区间和

    为了计算最后的 dp[1][n],需要考虑所有的可能的合并。这些合并包括:

    1. 合并之前,dp[i][i]=0, 1<=i<=n
    2. 两堆合并,如右图 

               例如:dp[1][2] = dp[1][1] + dp[2][2] + sum[1][2];

               总结:dp[i][i+1] = dp[i][i] + dp[i+1][i+1] + sum[i][i+1];

        3.       三堆合并,如右图所示

                 例如合并第 1 堆到第 3 堆,有两种情况,如右图所示

                 dp[1][3] = min( dp[1][1]+dp[2][3], dp[1][2]+dp[3][3] )+ sum[1][3];

                 总结:dp[i][i+2] = min( dp[i][i]+dp[i+1][i+2], dp[i][i+1]+dp[i+2][i+2] )+ sum[i][i+2];

        4.      推广:第 i 堆到第 j 堆的合并,如右图所示

                 dp[i][j] = min( dp[i][k] + dp[k+1][j] ) + sum[i][j-i+1], i<=k<=j。这就是状态转移方程

    下面代码中方法 Minval() 实现了上述计算过程,其中有 3 层循环:

    1. 最外面一层循环的变量 len 表示区间 [i,j] 的长度,从 2 到 n;
    2. 第二层枚举的起点位置 i 从 1 到 n-len,终点通过计算得到,j = i+len;
    3. 在区间 [i,j] 里枚举每个分割的位置 k

    代码(Java)

    public class Main
    {
        final int INF = 1 << 30;
        final int N = 300;
        int n;
        int[] sum = new int[N];
    
        private int Minval1(){
            int[][] dp = new int[N][N];
            for(int len=1; len<n; len++)   //len 是 i 和 j 之间的距离
                for(int i=1; i<=n-len; i++){   //从第 i 堆开始
                    int j = i + len;   //到第 j 堆结束
                    dp[i][j] = INF;
                    for(int k=i; k<j; k++)   //i 和 j 之间用 k 进行分割
                        dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                }
            return dp[1][n];
        }
    
        private int Minval2(){
            int[][] dp = new int[N][N], s = new int[N][N];
            for(int i=1; i<=n; i++){
                dp[i][i] = 0;
                s[i][i] = i;   //初始值
            }
            for(int len=1; len<n; len++)
                for(int i=1; i<=n-len; i++){
                    int j = i + len;
                    dp[i][j] = INF;
                    for(int k=s[i][j-1]; k<=s[i+1][j]; k++)   //缩小范围
                       if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1] < dp[i][j]){
                           dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                           s[i][j] = k;   //记录 [i,j] 的最优分割点
                       }
                }
            return dp[1][n];
        }
    
        public static void main(String args[]){
            Main m = new Main();
            Scanner sc = new Scanner(System.in);
            while(!sc.hasNext("#")){   //输入以“#”字符串结束
                m.n = sc.nextInt();
                m.sum[0] = 0;
                for(int i=1; i<=m.n; i++){
                    int x = sc.nextInt();
                    m.sum[i] = m.sum[i-1] + x;   //从 i 到 j 之间的 sum 值等于 sum[j]-sum[i-1] 
                }
                System.out.println(m.Minval1());
                System.out.println(m.Minval2());
            }
            sc.close();
        }
    }

    理解:区间 [0,n],对于 len=1 时,从 [i,i+1] 、[i+1,i+2]、……、[n-1,n]子区间找出最小花费,接下来对 len=2,从 [i,i+2]、[i+2,i+4]、……[n-2,n]子区间找出最小花费,接下来对于 len=3……,直到 len=n-1,就可找出 [0,n] 区间的最小花费,即为所求。

     对于方法 Minval1() (复杂度为 O(n^3))是可以优化的,在它的三层循环中,最后一层循环枚举分割点 k 是可以优化的:因为每次运行最后一层循环时都在某个子区间内部寻找最优分割点,该操作在多个子区间里是重复的。如果找到这个最优点后保存下来,用于下一次循环,就能避免重复计算,从而降低复杂度

    用 s[i][j] 表示区间 [i,j] 中的最优分割点,第三重循环可以从区间 [i,j-1] 的枚举优化到区间 [ s[i][j-1], s[i+1][j] ] 的枚举。其中 s[][] 值是在前面的第三重循环中已经找到并记录下来的。这样算法复杂度接近 O(n^2),可解决 n<3000 的问题 

    理解:[i,j] 的最优分割点 是介于 [i,j-1] 的最优分割点 与 [i+1,j] 的最优分割点 之间的

     

    2、回文串

    概念

    回文串是正读和反读都一样的字符串

    问题描述

    解题思路

    该题有多种解法,其中一种是把 s 反转得到 s',求得两者最长公共子序列的长度 l,用 s 的长度减去 l 就是答案。下面用区间 DP 方法求解:

    定义状态 dp[i][j] 表示字符串 s 的子区间 s[i,j] 变成回文串的最小花费

    另外,在考虑删除和插入的花费时,由于这两种操作是等价的(这头加和那头减一样,即都使之成为回文串),所以只要取这两种操作的最小值就可。用数组 w[] 定义字符的花费。

    有以下 3 种情况:

    1. 如果 s[i] == s[j],那么 dp[i][j] = dp[i+1][j-1],如右图:
    2. 如果 dp[i+1][j] 是回文串,那么 dp[i][j] = dp[i+1][j] + w[i],如右图:
    3. 如果 dp[i][j-1] 是回文串,那么 dp[i][j] = dp[i][j-1] + w[j].

    总结情况2、3,状态转移方程是:dp[i][j] = min( dp[i+1][j]+w[i], dp[i][j-1]+w[j] ) (理解:增或减去 s[i] 或 s[j],使原 [i,j] 区间成为回文串)

    该程序包含两层循环,外层 i 枚举子区间起点,内层 j 枚举终点。因为需要从小区间扩展到大区间,所以 i 从 s 的尾端开始,逐步回退扩大区间,直到首端

    代码(Java)

    public class Main {
       int n,m;
       int[] w = new int[30];
       int[][] dp = new int[2005][2005];
       char ch;
       char[] s = new char[2005];   //给定的字符串
    
        public static void main(String[] args) {
            int x,y;
            Scanner sc = new Scanner(System.in);
            while (!sc.hasNext("#")){ //以 # 字符串结束输入
               Main m = new Main();
               m.n = sc.nextInt();   //n 是用到的字符个数
               m.m = sc.nextInt();   //m 是 s 的长度
               sc.skip("\n");   //按照输入样例,需要过滤掉一个换行符
               m.s = sc.nextLine().toCharArray();
               for(int i=0; i<m.n; i++){
                   String str = sc.next();   //接受一个字符串
                   m.ch = str.charAt(0);   //读取每个字符的插入和删除的花费
                   x = sc.nextInt();
                   y = sc.nextInt();
                   m.w[m.ch-'a'] = Math.min(x,y);   //取其中的最小值
               }
               for(int i=m.m-1; i>=0; i--)   //i 是子区间的起点
                   for(int j=i+1; j<m.m; j++){   //j 是子区间的终点
                       if(m.s[i] == m.s[j])
                           m.dp[i][j] = m.dp[i+1][j-1];
                       else
                           m.dp[i][j] = Math.min(m.dp[i+1][j]+m.w[m.s[i]-'a'], m.dp[i][j-1]+m.w[m.s[j]-'a']);   //增或减去 s[i] 或 s[j],使原 [i,j] 区间成为回文串
                   }
               System.out.println(m.dp[0][m.m-1]);
            }
            sc.close();
        }
    }

     

     

     

     

     

     

     

     

     

    展开全文
  • 区间dp1

    2020-04-10 22:25:03
    //一般区间DP实现代码 memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++) //区间长度为1的初始化 dp[i][i] = 0; for (int len = 2; len <= n; len++) //枚举区间长度 { for (int i = 1, j = len; ...

    //一般区间DP实现代码
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) //区间长度为1的初始化
    dp[i][i] = 0;
    for (int len = 2; len <= n; len++) //枚举区间长度
    {
    for (int i = 1, j = len; j <= n; i++, j++) //区间[i,j]
    {
    //DP方程实现
    }
    }
    dp[i][j] i 是左区间 j是右区间

    memset(dp,0,sizeof(dp))//初始dp数组
    for(int len=2;len<=n;len++){//枚举区间长度
        for(int i=1;i<n;++i){//枚举区间的起点
            int j=i+len-1;//根据起点和长度得出终点
            if(j>n) break;//符合条件的终点
            for(int k=i;k<=j;++k)//枚举最优分割点
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程
        }
    }
    
    

    例题1:--------------------------------------------------------------------------------------
    【题目描述】
    在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。

    计算出将N堆石子合并成一堆的最小得分。

    【输入】
    第一行为一个正整数N (2≤N≤100);

    以下N行,每行一个正整数,小于10000,分别表示第i堆石子的个数(1≤i≤N)。

    【输出】
    一个正整数,即最小得分。

    【输入样例】
    7
    13
    7
    8
    16
    21
    4
    18
    【输出样例】
    239
    思路:
    不同的合并方式最后的结果也不同所以利用区间来考虑合并;dp[i][j]表示 合并i----j这个区间内的所有石子所花费的最小值
    那我们可以再去把 i–j细分啊 再去分成 i—k 和k+1----j 然后去跟dp[i][j]比较 赋给它最小值
    所以 dp式子为
    dp[i][j]=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];
    这里需要注意前缀和,每个值都为 a[i]+=a[i-1];
    比方说你想求 2-3的和 s=a[3]-a[2-1];

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    long long a[105], dp[105][105];
    int main()
    {
    	int n; cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> a[i]; a[i] += a[i - 1];
    	}
    	//dp[i][j] 表示合并i-j堆花费的最少费用
    	memset(dp, 0x3f, sizeof dp);//初始化的最大值写法
    	for (int i = 1; i <= n; i++)
    		dp[i][i] = 0;
    	for (int len = 2; len <= n; len++)
    	{
    		for (int i = 1, j = len; j <= n; i++,j++)
    		{
    			for (int k = i; k <= j; k++)
    			{
    				if (dp[i][j] > dp[i][k] + dp[k + 1][j] + a[j] - a[i - 1])
    					dp[i][j] = dp[i][k] + dp[k + 1][j] + a[j] - a[i - 1];
    			}
    		}
    	}
    	cout << dp[1][n] << endl;
    }
    

    例题二:------------------------------------------------------------------------------------
    括号匹配
    poj2955
    给一个括号组成的字符串,问最多能匹配多少个括号
    像([)]这样的字符串匹配度为2,但是像()[]、[()]的字符串匹配度为4,也就是说括号具有分隔作用。
    长度为1的串匹配度 0
    长度为2的串匹配度 0 或 2

    思路①
    dp[i][j]为i–j 之间的最大匹配度
    如果 i和j上的匹配 那么dp[i][j]=dp[i+1][j-1]+2;
    否则
    就再去分割区间 类似于上一个例题。

    for (int len = 2; len <= n; len++)
        {
            for(int i = 1, j = len; j <= n; i++, j++)
            {
                if((a[i]=='('&&a[j]==')') || (a[i]=='['&&a[j]==']'))
                    dp[i][j] = dp[i+1][j-1] + 2;
                for (int k = i; k < j; k++)
                    if(dp[i][j] < dp[i][k] + dp[k+1][j])
                        dp[i][j] = dp[i][k] + dp[k+1][j];
            }
        }
        printf("%d\n",dp[1][n]);
    }
    

    思路②
    涉及到了 第二种模型在这里插入图片描述
    在这里插入图片描述
    第二种模型就是根据匹配信息把区间划分成[i+1,k-1]和[k+1,j]

    for (int len = 2; len <= n; len++)
        {
            for(int i = 1, j = len; j <= n; i++, j++)
            {
                dp[i][j] = dp[i+1][j];
                for (int k = i; k <= j; k++)
                    if((a[i]=='('&&a[k]==')') || (a[i]=='['&&a[k]==']'))
                        dp[i][j] = max(dp[i][j], dp[i+1][k-1] + dp[k+1][j] + 2);
            }
        }
        printf("%d\n",dp[1][n]);
    

    例题3
    题意:有N个宴会,对于每一个宴会,女猪脚都要穿一种礼服,礼服可以套着穿,但是脱了的不能再用,参加宴会必须按顺序来,从第一个到第N个,问参加这些宴会最少需要几件礼服,拿第一个案例来说
    4
    1 2 1 2,有4个宴会,第一个需要礼服种类为1,第二个需要礼服种类为2,以此往下推:

    参加第一个宴会时穿礼服1,参加第二个时,礼服1不要脱下,直接把礼服2套在外面,参加第三个的时候把礼服2脱下即可,参加第四个则需要一件新的礼服了
    思路:
    dp[i][j]代表从区间i到区间j最少的穿衣数量,那么在dp[i][j]这个状态的穿衣数,就要等于dp[i+1][j]+1;也就是说,首先在不考虑它后面是否有一天要穿相同的衣服的情况下,它肯定会比区间i+1到j的衣服多出一件;

    然后,再考虑在这个区间范围,是否有一天要穿相同的衣服,i<k<=j,如果有第k天衣服和第i天的衣服是一样的,那么就要比较如果第i天不穿1件衣服与第i天穿上1件衣服;

    首先,第i天穿上一件衣服的结果已经得出,那么我们只需比较不穿衣服,那么就是dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);

    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    #include <algorithm>
    #include <math.h>
    #include <stdio.h>
     
    using namespace std;
    int n;
    int a[105];
    int dp[105][105];
    int main()
    {
        int t;
        scanf("%d",&t);
        int cas=0;
        while(t--)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            memset(dp,0,sizeof(dp));
     
            for(int i=n;i>=1;i--)
            {
                for(int j=i;j<=n;j++) 从后往前枚举,并且后面的最优解已经枚
                举过了,因为实际是从前往后进行,所以从后枚举不会造成影响
                {
                    dp[i][j]=dp[i+1][j]+1;  
                    先直接给他加上,因为说不
                    定这件衣服后面好多件都要用到
                    for(int k=i+1;k<=j;k++)
                    {
                        if(a[i]==a[k])
                        dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);  //这里不要是i+1,不是i,因为在讨论是不是脱i呢
                    }
                }
            }
            printf("Case %d: %d\n",++cas,dp[1][n]);
     
        }
        return 0;
    
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,468
精华内容 7,787
关键字:

区间dp