1 2 5 10 20 --> 800

用1元 2元 5元 10元 20元的钞票凑成800元的方法种数计算，使用了动态规划。

结果没打出来，只是保留在函数里各个vector中，调试可看所有结果。

优点：快

缺点：占空间占内存

耗时时间测试：

和为200：0.0022153191s

和为800：0.025958383s

和为1600：0.062776931s

和为3200：0.18964779s

下面是详细代码，能正常运行算出结果，改进空间很大，只列了思路。

算法为王，C写的O(n2)函数再快也不如R写的O（nlogn)函数。

void CMFCTestDlg::OnBnClickedBegin()

{

    UpdateData(TRUE);

    LARGE_INTEGER beginTime;

    QueryPerformanceCounter(&beginTime);

    std::vector<int> vec_1_2(m_nTotal+, -);

    for(int i=; i<=m_nTotal; i++)

    {

        vec_1_2[i] = +i/; // 使用1元 2元纸币组合成 0到m_nTotal 元的方法数

    }

    std::vector<int> vec_1_2_5(vec_1_2.begin(), vec_1_2.end());

    for(int i=; i<=m_nTotal; i++)

    {

        for(int j=; j<=i/; j++)

        {

            vec_1_2_5[i] += vec_1_2[i-j*]; // 使用1元 2元 5元纸币组合成 0到m_nTotal 元的方法数

        }

    }

    std::vector<int> vec_1_2_5_10(vec_1_2_5.begin(), vec_1_2_5.end());

    for(int i=; i<=m_nTotal; i++)

    {

        for(int j=; j<=i/; j++)

        {

            vec_1_2_5_10[i] += vec_1_2_5[i-j*]; // 使用1元 2元 5元 10元纸币组合成 0到m_nTotal 元的方法数

        }

    }

    std::vector<int> vec_1_2_5_10_20(vec_1_2_5_10.begin(), vec_1_2_5_10.end());

    for(int i=; i<=m_nTotal; i++)

    {

        for(int j=; j<=i/; j++)

        {

            vec_1_2_5_10_20[i] += vec_1_2_5_10[i-j*]; // 使用1元 2元 5元 10元 20元纸币组合成 0到m_nTotal 元的方法数

        }

    }


　　 //.... 如果有50元 100元等更多要求，在此处依次添加即可，很容易扩展

    LARGE_INTEGER endTime;

    QueryPerformanceCounter(&endTime);

    LARGE_INTEGER frequency;

    QueryPerformanceFrequency(&frequency);

    float fTime = (endTime.QuadPart-beginTime.QuadPart)/(float)(frequency.QuadPart);

    fTime = ;

}