动态规划学习记录

首先是入门级别的一维dp。

这个是凑硬币，如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

动态规划算法的核心是：每个子问题的状态和状态的转移方程。

状态是：dp[i] ，即凑够i元最少需要的硬币的个数

转移方程是：dp[i] = min(dp[i-C ₁ ]+1,dp[i-C ₂ ]+1,dp[i-C ₃ ]+1,……,dp[i-C _j ]+1])

即，每个状态的值都是最小的那个。

#include<stdio.h>
#define min(a,b) a<b?a:b
int main()
{
int c[3]={1,3,5};
int dp[100], i , j , k=999, n;
scanf("%d",&n);
dp[0] = 0;
for( i = 1 ;i <= n ; i++)
{ k = 999;//这里是关键，每次都要重新赋值。
for(j = 0 ; j < 3; j++)//把每种硬币的可能都找一遍
if(i >= c[j])
{
k = min(dp[i-c[j]]+1,k);
// printf("%d %d ",k ,c[j]);
//这是从三种硬币中找出最小硬币数的那个。
//dp中的数值是，到这个i的硬币数
}
dp[i]=k;
//printf("%d ",k);
//每次循环之后min都是最小的硬币数。
//这时无法区分他是用怎么的硬币构成
}

for( i = 0 ;i <= n ; i ++)
printf("%d元至少要%d个硬币 ", i, dp[i]);

}

下一题是lis就是最长非降子序列 longest increasing subsequence

5 3 4 8 6 7 找这个序列的最长非降子序列

很明显是 3 4 6 7 这个最长那么算法是要怎么找呢？

前1个数的lis长度 dp（1）= 1；序列 5

前2个数的lis长度 dp（2）= 1；序列 3 优先选小的，3前面没有比3小的了

前3个数的lis长度 dp（3）= 2；序列 3,4 dp（3） = dp（2） + 1

前4个数的lis长度 dp（4）= 3；序列 3,4,8 8前面3个都比他小，因此要判断

　　　　　　　　　　　　　　　　　　　dp（4）= max（dp（1），dp（2），dp（3））　　　　　　　　　　　　　　　　　　　　+1=3　

前5个数的lis长度 dp（5）= 3；序列 3,4,6这个同上

前6个数的lis长度 dp（6）= 4；序列 3,4,6,7 这个也是dp（6）=max（dp（4），　　　　　　　　　　　　　　　　　　　　　　dp（5））+1

所以要求dp（i），就把i之前的每一个子序列中，最后一个数不大于a【i】的序列长度+1 然后取出最大的长度就是dp（i）；如果i前面的各个子序列都大于a【i】，那么他就dp（i） = 1 ；

#include <iostream>
using namespace std;
int d[100];
int lis(int a[], int n)
{
int len = 1, i, j;
for(i = 0 ; i < n ; i++)
{//查询每一位置
d[i] = 1;
for(j = 0 ; j < i; j++)
//在当前位置之前的每一个位置
if(a[j] <= a[i] && d[j]+1 > d[i])
//把前面各个子序列中最后一个数不大于a【i】
d[i] = d[j] + 1;
//反复覆盖一个位置，
if(d[i] > len) len = d[i];
//每次留下最大的长度
}
return len;
}
int main()
{
int a[100],m,t,i;
cin>>m;

for(i = 0 ; i <m ; i++)
cin>>a[i];

cout << lis(a,m)<<endl;
return 0;
}

现在提升难度来个二维的dp　　

找苹果

平面上有m＊m个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。

先来找找状态每个格子只能从左边和上面下来，要知道这个位置的最大总苹果就判断上面和左边的苹果哪个大，从大的那边走，然后就是递归的来每一个找一遍。

难度不大。思维掌握就好了。

#include<stdio.h>
#define max(a,b) a > b ? a : b
int main()
{
int a[10][10] = {0},s[10][10] = {0};//数组最好大点
int n,m,i,j;
scanf("%d",&m);//正方形
for(i = 0 ; i < m; i ++)
for(j = 0 ; j < m ; j ++)
scanf("%d",&a[i][j]);
s[0][0]=a[0][0];
for(i = 1 ; i < m ; i++)
s[i][0] = a[i][0]+s[i-1][0];
for(j = 1 ; j < m ; j++)
s[0][j] = a[0][j]+s[0][j-1];
//这两个for是为了防止溢出先把边缘的计算出来。
for(i = 1 ; i < m ; i++)
for(j = 1 ; j < m ; j++)
{
s[i][j] = max(s[i-1][j],s[i][j-1]);
//这里是个坑，我也不知道为什么两个一起写就出错，
s[i][j] += a[i][j];
//分开就对了
//逻辑也简单就是判断上面和左边哪一个大，选大的一个
}

for(i = 0 ; i < m; i ++)
{
for(j = 0 ; j < m ; j ++)
printf("%d ",s[i][j]);
printf(" ");
}

}

数塔问题或者掉馅饼

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

 1 #include <stdio.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define max(a,b,c)     (a>b?a:b)>c ? (a>b?a:b) : c
 5 #define P 100001
 6 int a[P][13];
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d",&n)!=EOF&&n)
11     {
12         int i,p,t,k,j=-1;
13         memset(a,0,13*P*sizeof(int));
14         for(i=0;i<n;i++)
15          {
16              scanf("%d%d",&p,&t);
17              a[t][p+1]++;         /*位置后移一位*/
18              if(t>j)   j=t;           /*记录最大时间*/
19          }
20          for(i=j-1;i>=0;i--)       /*最终时间肯定是连续的1到j，（1到j，推断理解），（j到1，敲代码）*/
21          {
22              for(k=1;k<=11;k++)
23                 a[i][k]+=max(a[i+1][k-1],a[i+1][k],a[i+1][k+1]);   /*位置后移1位和数组开大2位的好处，k-1和k+1不会越界*/
24          }//每次和后面一行对应的上面的三个数比较最大的
25          printf("%d
",a[0][6]);
26      }
27      return 0;
28  }

思路嘛，还是一样，建立一个二维的状态表，每次往上面找，，不断用最好的来替换过去。。最后的结果就是最好的。

下面来个比较难一些的，叫矩形嵌套：

有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

http://acm.pdsu.edu.cn/problem.php?id=1171

第一行是一个正正数N(0<N<10)，表示测试数据组数，
每组测试数据的第一行是一个正正数n，表示该组测试数据中含有矩形的个数(n<=1000)
随后的n行，每行有两个数a,b(0<a,b<100。提示： (1,2)可以嵌套在（2,2）中，但不能嵌套在（2,1）中。)，表示矩形的长和宽

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int cmp(const void *a,const void *b)
{
    int* c = (int *)a;
    int* d = (int *)b;
    if(*c != *d)
       return *c - *d;
    return *(d+1) - *(c+1);
}
//二维排序，。

int main()
{
    int a[1010][5] ,b[1010],t,n,i,j,temp;
    scanf("%d",&t);
    while(t--)
    {
          scanf("%d",&n);
          for(i=0;i<n;i++)
          {
               scanf("%d%d",&a[i][0],&a[i][1]);
               if(a[i][0] > a[i][1])
               {
                  temp = a[i][0];
                  a[i][0] = a[i][1];
                  a[i][1] =temp;
               }
         }//输入
          qsort(a,n,sizeof(a[0]),cmp);
          int max=0;
          for(i=0;i<n;i++)
          {     max = 0;
                for(j=i-1;j>=0;j--)
                {
                    if(a[j][1]<a[i][1] && b[j]>max)
                       max = b[j];
                }
                b[i] = max + 1;
          }
          //dp的写状态
          int count = 0;
          for(i=0;i<n;i++)
             if(b[i] > count)
                count = b[i];
            //找最大值
          printf("%d
",count);
    }
    return 0;
}