<commit_before>---
layout: post
title: DP总结
category: Study
tags: Algorithm DP
---

对《算法导论 第3版》第15章——动态规划，15.1和15.2两个最优化问题的解决过程做笔记和思考。

#### 利用DP解题的基本步骤

1. 刻划一个最优解的结构特征；
2. 递归的定义最优解的值；
3. 计算最优解的值，通常采用自下向上的方法；
4. 利用计算的信息构造一个最优解。

#### 钢条切割

##### 刻画一个最优解的结构特征

将长度为\\(n\\)的钢条切割为\\(k\\)(\\(1 \leq k \leq n\\))段，那么最优的切割方案为：
\\[n=i_1+i_2+...+i_k\\]

将钢条切割为长度分别是\\(i_1,i_2,i_3,...,i_k\\)的小段，得到最大收益：
\\[r_n = p_{i_1} + p_{i_2} + p_{i_3} + ... + p_{i_k}\\]

##### 递归的定义最优解的值

根据上面给出的结构特征不难得出最优切割收益的递归公式：
\\[r_n = max(p_n,r_1 + r_{n - 1},r_2 + r_{n-2},...,r_{n-1} + r_1)\\]

关于此问题，我们还能简化递归公式。假设将钢条切割为两段，第一段始终为最优解，接着就只需递归求解第二段，此时得出更为简单的最优切割收益的递归公式：
\\[r_n = \max_{1 \leq i \leq n}(p_i + r_{n - i})\\]

##### 计算最优解的值

```c
/*
 * 求解最优切割收益的方案
 *
 * p: 价格表
 * n: 待切割钢条的长度
 * r: 保存钢条的最优收益
 * s: 保存最优切割方案的解
 */
int
bottom_up_cut_rod(int *p, int n, int *r, int *s)
{
        int i, j;
        int q;

        if (NULL == p || n < 0)
                return -1;
        
        r[0] = 0;
        for (j = 1; j <= n; j++) {
                q = -1;
                for (i = 1; i <= j; i++) {
                        if (q < p[i] + r[j - i]) {
                                q = p[i] + r[j - i];
                                s[j] = i;
                        }
                }

                r[j] = q;
        }

        return 0;
}
```

根据代码可以得出算法的时间复杂度为\\(\Theta (n^2)\\)，空间复杂度为\\(\Theta (n)\\)。

##### 构造一个最优解

```c
/*
 * 输出最优切割方案
 *
 * p: 价格表
 * n: 待切割钢条的长度
 */
void
print_cut_rod_solution(int *p, int n) {
        int *r, *s;

        if (NULL == p || n < 0)
                return;

        *r = (int *) malloc(sizeof(int) * (n + 1));
        if (NULL == *r)
                return -1;

        *s = (int *) malloc(sizeof(int) * (n + 1));
        if (NULL == *s) {
                free(*r);
                return -1;
        }

        if (bottom_up_cut_rod(p, n, &r, &s) == 0) {
                while (n > 0) {
                        printf("%d ", s[n]);
                        n = n - s[n];
                }

                printf("\n");
        } else
                printf("Error\n");
}
```

#### 矩阵链乘法

##### 最优括号话方案的结构特征

有这样一个矩阵链\\(A_{i.j}\\)表示\\(A_i A_{i+1} A_{i+2} ... A_j\\)，要找出最优括号方案，我们可以将矩阵链从某一个矩阵位置划分为两个子矩阵链，如果\\(A_k\\)(\\(i \leq k < j\\))即我们找的划分点，那么此时我们两个子据很链分别为\\(A_{i.k}\\)和\\(A_{k+1.j}\\)。我们应该对\\(A_{i.k}\\)和\\(A_{k+1.j}\\)分别独立求解，最终构造出问题的最优解。

##### 一个递归求解的方案

按照前面给出的结构特征，我们可以得出最优解的递归公式：
\\[m\[i,j\] = m\[i,k\] + m\[k + 1, j\] + p_{i - 1} p_k p_j\\]

为了检查所有可能的情况，可以完善递归公式，如下：
\\[m\[i,j\] = 
\\begin{cases} 
0& \\text{i = j} \\\\\\
\min_{i \leq k < j}(m\[i,j\] = m\[i,k\] + m\[k + 1, j\] + p_{i - 1} p_k p_j)& \\text{i < j}
\\end{cases}
\\]

##### 计算最优解代价

```c
/*
 * 求解矩阵链最优括号化方案
 *
 * p: 矩阵链行和列(n个矩阵,则p中应有n+1个值)
 * n: 矩阵个数
 * m: 保存最优扩化方案的代价
 * s: 保存最优括号化方案的解
 */
int
matrix_chain_order(int *p, int pn, int **m, int **s)
{
        int i, j, l, k, n;

        if (NULL == p || n < 0)
                return -1;

        if (NULL == m || NULL == *m ||
            NULL == s || NULL == *s)
            return -1;

        n = pn - 1;

        for (i = 0; i < n; i++)
                m[i][i] = 0;

        for (l = 2; l <= n; l++)
                for (i = 0; i < n - l + 1; i++) {
                        j = i + l - 1;
                        m[i][j] = INT_MAX;
                        for (k = i; k < j; k++) {
                                q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                                if (q < m[i][j]) {
                                        m[i][j] = q;
                                        s[i][j] = k;
                                }
                        }
                }

        return 0;
}
```

根据代码可以得出算法的时间复杂度为\\(\Omega (n^3)\\)，空间复杂度为\\(\Theta (n^2)\\)。

##### 构造一个最优解

```c
/*
 * 输出矩阵链最优括号化的解
 *
 * s: 保存最优括号化方案的解
 * i: 子问题最优括号化的起始位置(与j对应)
 * j: 自问提最优括号化的结束位置(与i对应)
 */
void
print_optimal_parens(int **s, int i, int j)
{
        if (i == j)
                printf("A%d", i);
        else {
                printf("(");
                print_optimal_parens(s, i, s[i][j]);
                print_optimal_parens(s, s[i][j] + 1, j);
                printf(")");
        }
}
```

{% include mathjax.html %}
<commit_msg>update 2017-10-20-dp.md<commit_after>---
layout: post
title: DP总结
category: Study
tags: Algorithm DP
---

对《算法导论 第3版》第15章——动态规划，15.1和15.2两个最优化问题的解决过程做笔记和思考。

#### 利用DP解题的基本步骤

1. 刻划一个最优解的结构特征；
2. 递归的定义最优解的值；
3. 计算最优解的值，通常采用自下向上的方法；
4. 利用计算的信息构造一个最优解。

#### 钢条切割

##### 刻画一个最优解的结构特征

将长度为\\(n\\)的钢条切割为\\(k\\)(\\(1 \leq k \leq n\\))段，那么最优的切割方案为：
\\[n=i_1+i_2+...+i_k\\]

将钢条切割为长度分别是\\(i_1,i_2,i_3,...,i_k\\)的小段，得到最大收益：
\\[r_n = p_{i_1} + p_{i_2} + p_{i_3} + ... + p_{i_k}\\]

##### 递归的定义最优解的值

根据上面给出的结构特征不难得出最优切割收益的递归公式：
\\[r_n = max(p_n,r_1 + r_{n - 1},r_2 + r_{n-2},...,r_{n-1} + r_1)\\]

关于此问题，我们还能简化递归公式。假设将钢条切割为两段，第一段始终为最优解，接着就只需递归求解第二段，此时得出更为简单的最优切割收益的递归公式：
\\[r_n = \max_{1 \leq i \leq n}(p_i + r_{n - i})\\]

##### 计算最优解的值

```c
/*
 * 求解最优切割收益的方案
 *
 * p: 价格表
 * n: 待切割钢条的长度
 * r: 保存钢条的最优收益
 * s: 保存最优切割方案的解
 */
int
bottom_up_cut_rod(int *p, int n, int *r, int *s)
{
        int i, j;
        int q;

        if (NULL == p || n < 0 || 
            NULL == r || NULL == s)
                return -1;
        
        r[0] = 0;
        for (j = 1; j <= n; j++) {
                q = -1;
                for (i = 1; i <= j; i++) {
                        if (q < p[i] + r[j - i]) {
                                q = p[i] + r[j - i];
                                s[j] = i;
                        }
                }

                r[j] = q;
        }

        return 0;
}
```

根据代码可以得出算法的时间复杂度为\\(\Theta (n^2)\\)，空间复杂度为\\(\Theta (n)\\)。

##### 构造一个最优解

```c
/*
 * 输出最优切割方案
 *
 * p: 价格表
 * n: 待切割钢条的长度
 */
void
print_cut_rod_solution(int *p, int n) {
        int *r, *s;

        if (NULL == p || n < 0)
                return;

        r = (int *) malloc(sizeof(int) * (n + 1));
        if (NULL == r)
                return -1;

        s = (int *) malloc(sizeof(int) * (n + 1));
        if (NULL == s) {
                free(r);
                return -1;
        }

        if (bottom_up_cut_rod(p, n, r, s) == 0) {
                while (n > 0) {
                        printf("%d ", s[n]);
                        n = n - s[n];
                }

                printf("\n");
        } else
                printf("Error\n");
}
```

#### 矩阵链乘法

##### 最优括号话方案的结构特征

有这样一个矩阵链\\(A_{i.j}\\)表示\\(A_i A_{i+1} A_{i+2} ... A_j\\)，要找出最优括号方案，我们可以将矩阵链从某一个矩阵位置划分为两个子矩阵链，如果\\(A_k\\)(\\(i \leq k < j\\))即我们找的划分点，那么此时我们两个子据很链分别为\\(A_{i.k}\\)和\\(A_{k+1.j}\\)。我们应该对\\(A_{i.k}\\)和\\(A_{k+1.j}\\)分别独立求解，最终构造出问题的最优解。

##### 一个递归求解的方案

按照前面给出的结构特征，我们可以得出最优解的递归公式：
\\[m\[i,j\] = m\[i,k\] + m\[k + 1, j\] + p_{i - 1} p_k p_j\\]

为了检查所有可能的情况，可以完善递归公式，如下：
\\[m\[i,j\] = 
\\begin{cases} 
0& \\text{i = j} \\\\\\
\min_{i \leq k < j}(m\[i,j\] = m\[i,k\] + m\[k + 1, j\] + p_{i - 1} p_k p_j)& \\text{i < j}
\\end{cases}
\\]

##### 计算最优解代价

```c
/*
 * 求解矩阵链最优括号化方案
 *
 * p: 矩阵链行和列(n个矩阵,则p中应有n+1个值)
 * n: 矩阵个数
 * m: 保存最优扩化方案的代价
 * s: 保存最优括号化方案的解
 */
int
matrix_chain_order(int *p, int pn, int **m, int **s)
{
        int i, j, l, k, n;

        if (NULL == p || n < 0)
                return -1;

        if (NULL == m || NULL == *m ||
            NULL == s || NULL == *s)
            return -1;

        n = pn - 1;

        for (i = 0; i < n; i++)
                m[i][i] = 0;

        for (l = 2; l <= n; l++)
                for (i = 0; i < n - l + 1; i++) {
                        j = i + l - 1;
                        m[i][j] = INT_MAX;
                        for (k = i; k < j; k++) {
                                q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                                if (q < m[i][j]) {
                                        m[i][j] = q;
                                        s[i][j] = k;
                                }
                        }
                }

        return 0;
}
```

根据代码可以得出算法的时间复杂度为\\(\Omega (n^3)\\)，空间复杂度为\\(\Theta (n^2)\\)。

##### 构造一个最优解

```c
/*
 * 输出矩阵链最优括号化的解
 *
 * s: 保存最优括号化方案的解
 * i: 子问题最优括号化的起始位置(与j对应)
 * j: 自问提最优括号化的结束位置(与i对应)
 */
void
print_optimal_parens(int **s, int i, int j)
{
        if (i == j)
                printf("A%d", i);
        else {
                printf("(");
                print_optimal_parens(s, i, s[i][j]);
                print_optimal_parens(s, s[i][j] + 1, j);
                printf(")");
        }
}
```

{% include mathjax.html %}

{'fraction_non_alphanumeric': 0.21712864250177683, 'fraction_numerical': 0.018005212035062782, 'mean_word_length': 1.306200491668943, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4856362', 'n_tokens_mistral': 4577, 'n_tokens_neox': 4817, 'n_words': 711}