动态规划学习1：669

动态规划学习1：669 · 换硬币

2023/12/1 18:32:18

有2元5元7元的硬币，要凑27元钱，求最少的硬币数目

动态规划题目特点

1.计数
——有多少种方式方式走到右下角
——有多少种方法选出k个数使得和是sum
2.求最值
——左上角走到右下角路径的最大数字和
——最长上升子序列长度
3.求存在性
——先手是否必胜
——能不能选出k个数使得和是sum

解题步骤

一.确定状态
●最后一步(最优策略中使用的最后一-枚硬币ak )
●化成子问题(最少的硬币拼出更小的面值27-ak )
二.转移方程
●f[X] = min{f[X- 2]+1, f[X-5]+1, f[X-7]+1}
三.初始条件和边界情况
●f[0] = 0,如果不能拼出Y , f[Y]=正无穷
四.计算顺序
●f[0], f[1], f[2],
确保方程中的的数是按顺序的
//递归版本

#include <bits/stdc++.h>
using namespace std;
int func(int coin){
    int amout = INT_MAX-1;
    if (coin == 0) return 0;
    if (coin >=2){
        amout = min(amout,func(coin - 2)+1);
    }
    if (coin >= 5){
        amout = min(amout,func(coin - 5)+1);
    }
    if (coin >= 7){
        amout = min(amout,func(coin - 7)+1);
    }
    return amout;
}
int main() {
    //递归版本
    cout << func(27);
    //动态规划版本
    int n = 0;
    cin >> n;
    int *amout = (int*)malloc((n+1)* sizeof(int));
    amout[0] = 0;
    for (int i = 1; i <=n; i++) {
        int m = INT_MAX-1;
        if (i-2>=0&&i-5<0){
            m = amout[i-2]+1;
        } else if(i-5 >=0&&i-7<0){
            m = min(amout[i-2]+1,amout[i-5]+1);
        } else{
            m = min(amout[i-2]+1,amout[i-5]+1);
            m = min(m,amout[i-7]+1);
        }
        amout[i] = m;
    }
    cout << amout[n] << endl;
    free(amout);
    return 0;
}

669 · 换硬币

描述

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

样例
样例1

输入：

[1, 2, 5]
11

输出： 3

解释： 11 = 5 + 5 + 1

样例2

输入：

[2]
3

输出： -1

样例3

输入：

[1, 9]
0

输出： 0

int coinChange(vector<int> &coin,int m){
    //初始情况和边界
    int *arr = new int[m+1];
    arr[0] = 0;
    int coin_length = coin.size();
    for (int i = 1; i <=m ; i++) {
        //边界
        arr[i] = INT_MAX;
        for (int j = 0; j < coin_length; j++) {
            //确定状态：f(x)min -> f(m-x)min
            if (i-coin[j]>=0&&arr[i-coin[j]]!=INT_MAX){
                //转移方程：f[x] = min(f[x-coin[0]],f[x-coin[1]],f[x-coin[2]])
                arr[i] = min(arr[i-coin[j]]+1,arr[i]);
            }
        }
        if (arr[m] == INT_MAX){
            arr[m] = -1;
        }
    }
    int num = arr[m];
    delete[] arr;
    return num;
}