LeetCode专栏之动态规划部分

• 2022年5月17日，来看下硬币https://leetcode.cn/problems/coin-lcci/ 问题，其实就是一个0-1背包问题

class Solution {
public:
    int waysToChange(int n) {
        // 0-1背包
        int dp[n+1];
        fill(dp,dp+n+1,0);
        int coins[] = {1,5,10,25};
        for (int i=0;i<4;++i) {
            for (int j=1;j<=n;++j) {
                if (coins[i] == j) {
                    dp[j] = (dp[j] + 1) % 1000000007;
                }else if (coins[i] < j) {
                    dp[j] = (dp[j] + dp[j-coins[i]]) % 1000000007;
                }
            }
        }
        return dp[n];
    }
};