DP 之 CODE[VS] 1048 石子归并（两种实现方式：递归，循环）

dp[i][j] : i到j，最小代价
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j])
(注：i < k < j)

方式一：

 1 // 递归（好理解）
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <locale>
 7 #include <cmath>
 8 using namespace std;
 9 const int INF = 0x3f3f3f3f;
10 const int MaxN = 105;
11 
12 int N, dp[MaxN][MaxN], sum[MaxN][MaxN];
13 
14 
15 int Solve(int tbegin, int tend) {
16     if (dp[tbegin][tend] != INF) return dp[tbegin][tend];
17     for (int k = 0; (tbegin + k) < tend; ++k)
18     {
19         dp[tbegin][tend] = min(dp[tbegin][tend],
20             Solve(tbegin, tbegin + k) + Solve(tbegin + k + 1, tend) + sum[tbegin][tend]);
21     }
22     //cout << tbegin << "-->" << tend << " : " << dp[tbegin][tend] << endl;
23     return dp[tbegin][tend];
24 }
25 
26 int main() {
27     
28     cin >> N;
29     for (int i = 0; i < N; ++i)
30     {
31         cin >> sum[i][i];
32         for (int j = 0; j < i; ++j)
33         {
34             sum[j][i] = sum[j][i - 1] + sum[i][i];
35         }
36     }
37     for (int i = 0; i < N; ++i)
38     {
39         for (int j = 0; j < N; ++j)
40         {
41             if (i == j) dp[i][j] = 0;
42             else dp[i][j] = INF;
43         }
44     }
45     cout << Solve(0, N-1) << endl;
46 
47 
48 #ifdef HOME
49     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
50 #endif
51     return 0;
52 }

方式二：

 1 // 循环
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <locale>
 7 #include <cmath>
 8 using namespace std;
 9 const int INF = 0x3f3f3f3f;
10 const int MaxN = 105;
11 
12 
13 
14 int N, dp[MaxN][MaxN], sum[MaxN][MaxN];
15 
16 
17 void Solve() {
18     if (N == 1)
19     {
20         cout << sum[0][0] << endl;
21         return;
22     }
23 
24     for (int i = 0; i < N; ++i)
25     {
26         for (int j = 0; j < N; ++j)
27         {
28             if (i == j) dp[i][j] = 0;
29             else dp[i][j] = INF;
30         }
31     }
32 
33     for (int k = 1; k < N; ++k)
34     {
35         for (int i = 0; (i + k) < N; ++i)
36         {
37             for (int j = i; j < i + k; ++j)
38             {
39                 dp[i][i + k] = min(dp[i][i + k], dp[i][j] + dp[j + 1][i + k] + sum[i][i+k]);
40                 //cout << i << "-->" << i + k << " : " << dp[i][i + k] << endl;
41             }
42         }
43     }
44     cout << dp[0][N - 1] << endl;
45 }
46 
47 int main() {
48     
49     cin >> N;
50     for (int i = 0; i < N; ++i)
51     {
52         cin >> sum[i][i];
53         for (int j = 0; j < i; ++j)
54         {
55             sum[j][i] = sum[j][i - 1] + sum[i][i];
56         }
57     }
58     Solve();
59 
60 
61 #ifdef HOME
62     cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;
63 #endif
64     return 0;
65 }

DP 之 CODE[VS] 1048 石子归并 （两种实现方式：递归，循环）

DP 之 CODE[VS] 1048 石子归并（两种实现方式：递归，循环）