This is the basic problem of complete knapsack , Simulate money exchange , At first, the equation of state was written wrong , I write directly dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3], Then I thought about it. It felt too big , Not quite right , Later, looking at the code on the Internet, I saw two layers for loop , It's basically the same , Why am I wrong , And then I simulated a little example by hand , Find out , This state transfer equation is very heavy , Add a lot of repetitions , Because it's all backpacks and 01 The difference between backpack code , It's the second floor for The order of the cycle , So this question is no exception , This is a complete knapsack , Because it has unlimited access to , The code is as follows

 #include <iostream>
#include <cstring> using namespace std;
const int N = ;
long long dp[N];
int main()
{
// Preprocessing
dp[] = ;
for (int i = ; i <= ; i++)
{
for (int j = i; j <= N; j++)
dp[j] += dp[j - i];
}
int n;
while (cin >> n)
{
cout << dp[n] << endl;
} return ;
}

HDU -1284 More articles on money exchange

  1. HDU 1284 Money exchange issues ( It's all backpacks : Introductory questions )

    HDU 1284 Money exchange issues ( It's all backpacks : Introductory questions ) http://acm.hdu.edu.cn/showproblem.php?pid=1284 The question : In one country there are only 1 branch ,2 branch .3 Cent , Put the money N ( ...

  2. HDOJ(HDU).1284 Money exchange issues (DP Completely backpack )

    HDOJ(HDU).1284 Money exchange issues (DP Completely backpack ) Problem analysis Naked complete knapsack problem Code Overview #include <iostream> #include <cstdio> ...

  3. HDU 1284 Money exchange issues The generating function 、DP

    Topic link :HDU 1284 Money exchange issues Money exchange issues Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J ...

  4. HDU 1284 Money exchange issues ( Ordinary type An infinite number of generating functions )

    Portal : http://acm.hdu.edu.cn/showproblem.php?pid=1284 Money exchange issues Time Limit: 2000/1000 MS (Java/Others)    ...

  5. hdu 1284 Money exchange issues Completely backpack

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=1284 The recursive formula :dp[i] = sum(dp[i], dp[i-C]) /* Money exchange issues Time ...

  6. hdu 1284 Money exchange issues ( Recurrence || DP || The generating function )

    Money exchange issues Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  7. HDU 1284 Money exchange issues ( Completely backpack )

    Money exchange issues Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  8. HDU 1284 Money exchange issues ( Dynamic programming The number of knapsack schemes )

    Money exchange issues Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

  9. Problem solving report :hdu 1284 Money exchange issues ( Simple mathematics orDP)

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=1284 Problem Description In one country there are only 1 branch ,2 branch ,3 Cent , Put the money N It's very difficult to change into coins ...

  10. 【 Completely backpack 】HDU 1284 Money exchange issues

    Problem Description In one country there are only 1 branch ,2 branch ,3 Cent , Put the money N There are many ways to change into coins . Please program out how many kinds of conversion methods there are . Input There is only one positive integer per line N,N Less than 32768. Out ...

Random recommendation

  1. stay php in , How to put a label in a page , Replace with what the user wants to output

    Preface : Busan trip , Expose human nature , ———————————————————————————————————————————————————————————————————————————— Let's take the simplest example today ...

  2. Multiple div One line processing

    1. Mode one : adopt div Of float attribute , Define the width , Then define float Properties and width Properties of , Implement multiple div Show on one line : 2. Mode two : adopt div Of display Properties of , At least 2 become div Of displ ...

  3. sharepoint 2010 List data paging control introduction pagination UserControl

    turn :http://blog.csdn.net/chenxinxian/article/details/8714391 Here is mainly to introduce the latest development of a sharepoint Paging controls for lists or document libraries , And the ...

  4. spring boot The use of springfox swagger Exhibition restful Of api doc

    Abstract springfox swagger Exhibition restful Of api doc, swagger is A POWERFUL INTERFACE TO YOUR API. The new file : import org ...

  5. Spring MVC View parser for

    Spring MVC The provided View parser uses ViewResolver View resolution , Implement rendering model in browser .ViewResolver Able to parse JSP.Velocity Templates .FreeMarker Templates and XSLT Equivalency ...

  6. MySQL Learning notes ( Four ): Choice of storage engine

    One : Summary of several common storage engines Two : How to choose In a word : Unless required InnoDB Features not available , And there's no alternative , Otherwise, priority should be given to InnoDB: perhaps , Unwanted InnoDB Characteristics of , And other engines are more suitable for the current situation ...

  7. ios Summary of knowledge points ——UITableView The expansion and contraction and transverse direction of Table

    UITableVIew yes iOS One of the most widely used controls in development , about UITableView This article will not discuss the basic usage of , This article mainly aims at UITableView The expansion and contraction of , In the end of the article, we will also discuss the horizontal ta ...

  8. vue stay .vue Listen to the routing in the file

    Monitor route   watch   $route vue In the project App.vue  file <template> <div id="app"> <!--includ ...

  9. centos7 Under no iptables

    from centos7 Start using linux, I didn't know much about the previous version , We're going to open a port today , Need to have firewall related operations , Looking up information from the Internet is an editor /etc/sysconfig Under directory iptables file , But I entered this file ...

  10. To borrow HTML5 Insert the video . Audio

    HTML5 Provides for the passage of video Element to contain the standard method of video . Insert the video <video width="320" height="240" contro ...