动态规划算法（C语言实现）

动态规划算法通常用于解决多阶段决策最优化的问题。这里的“动态”，指的是在解决多阶段决策的问题时，按照某一顺序，根据每一步在所选决策过程中引起的状态转移，最终在这种变化的状态中产生一个决策序列。

在这类问题中，可能会有许多可行解。每一个可行解都对应一个值，我们希望找到具有最优值的解。

C语言简单动态规划

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后将这些子问题的解合并得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是相互独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就能够避免大量的重复计算，进而节省大量时间。

C语言动态规划算法

我们可以用一个表来记录所有已解的子问题的解。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划算法的基本思路。

1) 采用动态规划算法求解的问题一般要具有 3 个性质。

①最优化原理

如果某个问题的最优解所包含的子问题的解也是最优的，那么就称该问题具有最优子结构，即满足最优化原理。也就是说求解一个问题的最优解是取决于求解其子问题的最优解。

一个问题非最优解对它问题的求解没有影响。简而言之，一个最优化策略的子策略总是最优的。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划算法计算。

②无后效性

即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，该状态以后的过程不会影响以前的状态，只与当前状态有关。

③有重叠子问题

即子问题之间是不独立的，一个子问题在下一阶段决策中可能会被多次使用到（该性质不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势)。

2) 动态规划算法的基本步骤如下。

• 分析最优解的性质，并刻画其结构特征。
• 递归定义最优解。
• 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
• 根据计算最优值时得到的信息，构造问题的最优解。

C语言动态规划应用示例

输入 n 个整数组成的一个序列 a 1，a 2，…，an，求该序列的子段和的最大值（当所有整数均为负数时，定义其最大子段和为0）。代码如下：

#include <stdio.h>
#include <stdlib.h>
int max_sum(int a[],int n,int *best_x,int *best_y)  /* *best_x表示最大子段和起点下标*/
{                                              /* *best_y表示最大子段和终点下标*/
    int x;
    int y;
    int this_sum[100];    
    int sum[100];
    int max = 0;          
    this_sum[0] = 0;       
    sum[0] = 0;
    *best_x = 0;
    *best_y = 0;
    x = 1;
    for(y=1;y<=n;y++)
    {
        if(this_sum[y-1]>=0)   /*如果添加元素前，序列的子段最大和为负，那么不管即将添加的元素为多少都只需将之前的子序列舍弃，直接取该元素的值作为新序列的子段最大和即可*/
           this_sum[y] = this_sum[y-1]+a[y];
        else                              
        {
           this_sum[y] = a[y];
           x = y;
        }
        if(this_sum[y]<=sum[y-1])    /*当加到一定程度，正负抵消到现在的子段最大和大于之前的子段最大和，就将现在的子段最大和作为最大值*/
           sum[y] = sum[y-1];
        else
        {
           sum[y]=this_sum[y];
           *best_x = x;
           *best_y = y;
           max = sum[y];
        }
    }
    return max;
}
int main()
{
    int i,j,num,a[100],t;
    printf("请输入数列个数（<100）:\n");
    scanf("%d",&num);
    printf("请输入数列元素:\n");
    for(i=1;i<=num;i++)
       scanf("%d",&a[i]);
    i=j=1;
    t=max_sum(a,num,&i,&j);
    printf("最大子段和是：%d\n",t);
    printf("子段起点是：%d\n",i);
    printf("子段终点是：%d\n",j);
    system("PAUSE");
    return 0;
}

运行结果：

请输入数列个数（<100）:
8
请输入数列元素:
-1
2
5
4
-7
6
8
-2
最大子段和是：18
子段起点是：2
子段终点是：7

本例使用动态规划算法可以将序列的各个子段的和记录到一个子段和的数组中，然后比较子段和数组中的元素，从而得到最大子段和。