找零钱的方案问题

原理和练习：https://www.nowcoder.com/questionTerminal/84ada2d688334355bf5cf07d394a59ca?orderByHotValue=2&questionTypes=000100&done=0&pos=1&onlyReference=false

#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
    int n =26;
    int changes[5] = { 1,5,10,25,50 };
    int **dp = new int*[5];
    for (int i = 0; i <5; i++) {
        dp[i] = new int[n + 1]();
    }
//生成dp数组
    for (int i = 0; i <5; i++) {
        if(i % dp[0] == 0)
        dp[i][0] = 1;
    }
//初始化第一行
    for (int j = 0; j <n + 1; j++) {
        dp[0][j] = 1;
    }
//初始化第一列
    for (int i = 1; i <5; i++) {
        for (int j = 1; j <n + 1; j++) {
            int num = 0;
            for (int k = 0; k*changes[i] <= j; k++) {
                num += dp[i - 1][j - k * changes[i]];
            }
            dp[i][j] = num;
        }
    }
    cout << dp[4][n];
    return 0;
}

优化部分的理解：

IMG_20180915_111655.jpg