青索

用户名：qingsuo123

访问量：579

签　名：

等　　级
排　　名	6963
经　　验	1358
参赛次数	2
文章发表	2
年　　龄	0
在职情况	学生
学　　校	洛阳师范学院
专　　业

　　自我简介：

TA的其他文章

动态规划（闫氏DP）合并石子
浏览：411

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

动态规划（闫氏DP）合并石子

　　作者: 青索　　　　发表时间：2022-04-07 21:20:46 浏览：411　|　评论：1　

原题链接：蓝桥杯算法提高VIP-合并石子

**思路：**石子合并到最后一定是左边一堆和右边一堆进行合并，所以当最后两堆石子花费都为最小时，合并成为的新一堆石子的花费也是最小的
所以状态转移方程：
**dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);**
dp[i][j]表示i到j堆石子合并的花费
s[n]表示前n堆石子的总和

难理解的可以搜一下闫氏DP
	#include<stdio.h>
    #include<string.h>
    int min(int a,int b)
    {
        if(a>=b)
            return b;
        else
            return a;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        int s[n];
        memset(s,0,sizeof s);
        int dp[n+1][n+1];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            s[i]=s[i]+s[i-1];
        }
        memset(dp,0,sizeof dp);
        for(int len=2;len<=n;len++)//区间长度
        {
            for(int i=1;i+len-1<=n;i++)//区间起点
            {
                int j=i+len-1;
                dp[i][j]=0x3f3f3f3f;//赋值无穷大，方便比较
                for(int k=i;k<j;k++)//区间终点
                {
           dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
                }
            }
        }
        printf("%d",dp[1][n]);
    	return 0;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

验题君

这个闫氏DP就狠6~

2022-04-12 08:23:02

青索

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

九宫重排（C++代码）

矩阵乘法（C++代码）

动态规划（闫氏DP）合并石子

评论区

精彩推荐

【密码】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

字符逆序（C语言代码）

DNA （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

整除问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

青索

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

九宫重排 （C++代码）

矩阵乘法 （C++代码）

动态规划（闫氏DP）合并石子

评论区

精彩推荐

【密码】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

字符逆序 （C语言代码）

DNA （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

整除问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

九宫重排（C++代码）

矩阵乘法（C++代码）

　　评论区

【密码】（C语言代码）

字符逆序（C语言代码）

整除问题（C语言代码）