动态规划——合并石子（C语言解）

第一次接触到动态规划是在斐波那契数列，那个时候还不知道动态规划的概念，由于数据量较小，直接用for循环就通过了，直到遇到了”合并石子“这道题目，百度过很多的文章都没看懂，大佬们都讲得太抽象了，一上来就是状态改变方程，算法小白一脸懵逼。经过一段时间的理解我终于搞懂了这道题目，下面说一说我的解法（可能不是最佳解法），希望能帮到大家。

动态规划的概念

首先我们要搞懂什么是动态规划。我觉得动态规划就是把一个大问题分解为多个小问题，每个小问题的决策都会影响到下一个小问题的决策。（下一个小问题的决策就是由上一个小问题的决策而产生的。）一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。

题目和思路

在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请设计一个程序，计算出将N堆石子合并成一堆的最小得分。

我们首先来分析一个比较简单的问题，现在一共有三堆石头，每堆石子的数量分别是3，4，11。求合并成一堆石头的最小得分。
对于这个问题，只有两种选择：
前两堆石头合并再和第三堆石头合并。
3+4=7 ——> 7 石堆变为（7， 11）
7+11=18——>18 石堆变为（18）
cost=7+18=25
后两堆石头合并再和第一堆石头合并。
4+11=15——>15 石堆变为（3，15）
3+15=18——>18 石堆变为（18）
cost=15+18=33

易看出先合并前两堆的石子的花费比较小，不同的合并方式会造成不同的得分。同时可以发现这两种方法最后一次的得分就是石头的总数。
现在我们用一个数组arr[]按顺序保存每个位置的石头数量。
arr[]={3,4,11}

二维数组sum[i][j]表示第i堆石头到第j堆石头的总和
sum[0][1]=3+4=7;
sum[1][2]=4+11=15;
sum[0][2]=3+4+11=18;

最后用一个二维数组dp[i][j]表示从第i堆到第j堆石头合并的最小分数。
1）每堆石头跟自己合并的分数都是0。
dp[0][0]=dp[1][1]=dp[2][2]=0
2）相邻两堆石头的最小合并分数只有一种可能。
dp[0][1]=3+4=7, dp[1][2]=4+11=15
3）剩下的就是不相邻石头的合并最小花费。
设一个k∈[i,j]；
dp[i][j]=dp[i][k]+dp[k][j]+sum[i][j];
那么从i到j的所有花费都可以表示出来了,取一个使得dp[i][j]最小的值。
我们用表格来表示出从i到j的费用最小值。（对于C来说一般是序号从0开始）

dp[1][3]=min(dp[1][1]+dp[2][3] , dp[1][2]+dp[3][3])+sum[1][3];
dp[2][4]=min(dp[2][3]+dp[4][4] , dp[2][2]+dp[3][4])+sum[2][4];
dp[1][4]=min(dp[1][1]+dp[2][4],dp[1][2]+dp[3][4],dp[1][3]+dp[4][4])+sum[1][4];
我们最终的目的是求出dp[1][4],那我们就要先求出dp[1][3]和dp[2][4],从图像上我们要求最右上角的值，就是沿着副对角线一步步往上求。

思路就是这样了，下面是代码。

具体代码

#include <stdio.h>
int main()
{int n,i,j,t,a,b;int arr[100];     int sum[100][100],dp[100][100];scanf("%d",&n);for (i=0; i<n; i++) {scanf("%d",&arr[i]);         //储存初始的每个位置的石头数量}for (i=0; i<n; i++) {for (j=i; j<n; j++) {if (i==j) {sum[i][j]=arr[i];     }elsesum[i][j]=sum[i][j-1]+arr[j];}  }                                //计算从i到j的石头总和for (i=0; i<n; i++) {dp[i][i]=0;if (i<n-1) {dp[i][i+1]=arr[i]+arr[i+1];  }}                     //把同一堆石头和相邻两堆石头合并的值计算for (t=2; t<=n; t++) {for (i=0; i<n-t; i++) {a=dp[i][i+t-1]+sum[i][i+t];b=dp[i][i]+dp[i+1][i+t]+sum[i][i+t];for (j=1; j<t-1; j++) {if (b>dp[i][i+j]+dp[i+j+1][i+t]+sum[i][i+t]) {b=dp[i][i+j]+dp[i+j+1][i+t]+sum[i][i+t];}}if (a<=b) {dp[i][i+t]=a;}elsedp[i][i+t]=b;}}            //按照表格从副对角线往依次计算的方法，最后求出右上角的值printf("%d",dp[0][n-1]);return 0;
}

有更好的方法欢迎交流～～
想学动态规划的可以看看这篇文章：告别动态规划，连刷40道动规算法题，我总结了动规的套路。