文章目录

• 问题一
• • • 问题描述
    • 递归方法
    • 动态规划版本

问题一

问题描述

题中给定数组[1,3,5,2]的面值，需要凑出面值为8，列表中的面值可以任意张数，有几种方法；

递归方法

/*----------------------------------------------------------------------
	> File Name: base.cpp
	> Author: Jxiepc
	> Mail: Jxiepc
	> Created Time: Sun 20 Mar 2022 08:44:42 AM CST
----------------------------------------------------------------------*/

#include <iostream>


int solve(std::vector<int> vc, int idx, int rest) {
    if(idx == vc.size()) {
        return rest == 0 ? 1 : 0;
    }

    int ways = 0;

    for(int num = 0; vc[idx] * num <= rest; ++num) {
        ways += solve(vc, idx + 1, rest - arr[idx] * num);
    }
    return ways;
}

int main(int argc, char* argv[])
{
    std::vector<int> vc = {1, 3, 5, 2};
    int aim = 8;
    solve(vc, 0, 8);
    return 0;
}

动态规划版本

/*----------------------------------------------------------------------
	> File Name: dynamic.cpp
	> Author: Jxiepc
	> Mail: Jxiepc
	> Created Time: Sun 20 Mar 2022 09:22:31 AM CST
----------------------------------------------------------------------*/

#include <vector>
#include <iostream>


int solve(std::vector<int> vc, int aim) {

    int len = vc.size();
    int arr[len + 1][aim+1] = {0};
    arr[len][0] = 1;

    for(int idx = len-1; idx >= 0; --idx) {
        for(int rest = 0; rest <= aim; ++rest) {
            arr[idx][rest] = arr[idx + 1][rest];
            /* 前面的格子不能越界 */
            if((rest -vc[idx]) >= 0)
                arr[idx][rest] += arr[idx][rest - vc[idx]]; 
        }
    }
    return arr[0][aim];
}

int main(int argc, char* argv[])
{
    std::vector<int> vc = {1, 3, 5, 2};
    int aim = 8;
    std::cout << solve(vc, 8) << std::endl;
    return 0;
}