本文共 3381 字，大约阅读时间需要 11 分钟。

1；了解一下DP的基本原理

其中的入门题；

我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时，仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！耐心点，让我们看看i=3时的情况。当i=3时，我们能用的硬币就有两种了：1元的和3元的( 5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了：凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是，我拿1个3元的硬币。好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。OK，码了这么多字讲具体的东西，让我们来点抽象的。从以上的文字中，我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，这个状态是怎么找出来的呢？我在另一篇文章 动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错，它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;有了状态和状态转移方程，这个问题基本上也就解决了

#include
   
    int main(){    int i, n, j,dp[25];    int b[3]={
  1,3,5};//三种硬币数；；；     while(scanf("%d",&n) != EOF)    {        for(i = 0; i <= n; i++)        {            dp[i] = i;            for(j = 0; j < 3; j++)            {                if(i >= b[j] && dp[i-b[j]]+1 < dp[i])//状态方程；；                 {                    dp[i] = dp[i-b[j]]+1;                }            }        }        printf("%d\n",dp[n]);    }    return 0 ;}
   

2最长上升子序列；；；；

状态转移方程得到：

#include
   
    int main(){    int n, i, j, len;    int dp[10004],a[10004];    while(~scanf("%d",&n))    {        for(i = 1; i <= n; i++)        {            scanf("%d",&a[i]);        }        dp[0] = 0;        len = 1;        for(i = 1; i <= n; i++)        {            dp[i] = 1;            for(j = i-1; j >= 1; j--)            {                if(a[j] < a[i] && dp[j]+1 > dp[i])                    dp[i] = dp[j]+1;            }            if(len < dp[i])            {                len = dp[i];            }        }        printf("%d\n",len);    }    return 0;}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////#include
    
     int main(){    int n , i, t, left,right,middle;    int a[10004],b[10004];     while(~scanf("%d",&n))    {        for(i = 1 ; i <= n; i++)        {            scanf("%d",&a[i]);         }         b[1] = a[1];        t = 1;        for(i = 2; i <= n; i++)        {            if(a[i] > b[t])            {                t++;                b[t] = a[i];            }             else            {                left = 0, right = t;                while(left <= right)                {                    middle = right-(right-left)/2;                    if(b[middle] >= a[i])                    {                        right = middle-1;                    }                     else                        left = middle+1;                }                b[left] = a[i];            }         }        printf("%d\n",t);     }    return 0 ;}
    
   

转载地址：https://blog.csdn.net/zw1996/article/details/52155453 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！