DP algorithm to solve problem 3014 on poj.org by C++

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了DP algorithm to solve problem 3014 on poj.org by C++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2437字，纯文字阅读大概需要4分钟。

内容图文

1. For this problem, there are 3 ways to solve, two DP algorithms to solve and one mathematical way to solve.

2. Question meaning：Put m pieces of cakes into n plates, a plate can have 0 or multiple pieces of cakes, how many ways are there?
   (for more specific explanations for the question, please search problem 3014 in poj.org)

   3. Common DP algorithm:
      (1) If the question is the number of ways to put m plates into n pieces of cakes, we use dp[m][n] to express.
      (2) For normal dp[i][j], means the number of ways to put m pieces of cakes into n plates, after we solve all dp[i][j], we can get dp[m][m].
      (3) We need to think how can we get dp[i][j], which the question is being changed to a classification problem, and the core to solve it is the
      state transition equation.

   4. Method 1: DP algorithm
      (1) Firstly, we need to compare the number of cakes with the number of plates, which we can get 3 cases:
      plates > cakes, plates = cakes, plates < cakes.
      For each case, we need to condider whether there are empty plates or not.
      (2) Case 1: plates > cakes
      For this case, there must have empty plates, and even if you take one plates away it does not matter, which can expressed as
      dp[i-1][j]. (remenber, i repsents plates and j represents cakes)
      Case 2: plates = cakes
      There are two sub-cases to consider.
      Firstly, there are no empty plates, which means each plate has exactly one piece of cake. And this only has 1 case.
      Secondly, there are empty plates. Same as case 1, it’s OK for take away at least one plates since there are empty plates,
      which can be expresses as dp[i-1][j].
      In total, there are 1 + dp[i-1][j] cases for case 2.
      Case 3: plates < cakes
      There are two sub-cases.
      Firstly, there are no empty plates. Same as before, it can be expressed as dp[i-1][j] since at least take away one plate
      does not matter.
      Secondly, there are empty plates. We can think as for each plate put 1 cake from j cakes, specificially, at i plate, there
      are j-i cakes left, since i cakes are consumed, which we can expressed as dp[i][j-i].

   5. Original problem: http://poj.org/problem?id=3014

   6. Code:
      #include
      using namespace std;
      int dp[4503][4503];
      int main()
      {
      int m,n,i,j;
      scanf("%d%d",&m,&n);
      dp[1][1]=1;
      dp[1][0]=0;
      dp[0][1]=0;
      for(i=1;i<=m;i++)
      {
      for(j=1;j<=n;j++)
      {
      if(i>j)
      dp[i][j]=dp[i-1][j];
      if(i==j)
      dp[i][j]=dp[i-1][j]+1;
      if(i<j)
      dp[i][j]=dp[i-1][j]+dp[i][j-i];
      if(dp[i][j]>=1000000007)
      dp[i][j]-=1000000007;
      }
      }
      printf("%lld\n",dp[m][n]);
      return 0;
      }

内容总结

以上是互联网集市为您收集整理的DP algorithm to solve problem 3014 on poj.org by C++全部内容，希望文章能够帮你解决DP algorithm to solve problem 3014 on poj.org by C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端