从放苹果问题到零钱兑换问题（动态规划）

ゞ浴缸里的玫瑰 2023-01-15 15:27 163阅读 0赞

# 放苹果问题 #

题目描述

> 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
> 
> 数据范围：0<=m<=10，1<=n<=10。

> 输入描述:输入两个int整数
> 
> 输出描述:输出结果，int型

示例1

> 输入：7 3
> 
> 输出：8

举例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 4][]

**总结：**

> 1.  m=0，没有苹果，所有盘子空着，一种放法，即f(0,n) = 1;
> 2.  n=0，没有盘子，没办法放，即f(m,0) = 0;
> 3.  m=1，一个苹果，只有一种放法，即f(1,n) = 1;
> 4.  n=1，一个盘子，只有一种放法，即f(m,1) = 1；
> 5.  m<n，盘子比苹果多，多余的盘子不起作用，即f(m,n)=f(m,m);
> 6.  每次放苹果都有两种放法可以选择，总的放法等于二者之和：f(m,n)=f(m,n-1)+f(m-n,n)

## 递归解法 ##

//递归写法
    int f(int m, int n){
        if(m <0 || n < 0){
            return 0;
        }
        if(n == 0) return 0;
        if(m == 0) return 1;
        if(m == 1 || n == 1) return 1;
        return f(m-n,n) + f(m,n-1);
    }

## 动态规划 ##

根据已知条件可写出状态方程：

>  *  f(0,n) = 1;
>  *  f(m,0) = 0;
>  *  f(1,n) = 1;
>  *  f(m,1) = 1；
>  *  f(m,n)=f(m,m)，m<n
>  *  f(m,n)=f(m,n-1)+f(m-n,n)

//动态规划
            int dp[11][11]= {0};
            //初始化
            for(int i=0; i<=m; ++i){
                for(int j=0; j<=n; ++j){
                    if(i==1 || j ==1 || i==0){
                        dp[i][j] = 1;
                    }else if(i-j <0){
                        dp[i][j] = dp[i][i];
                    }else{
                        dp[i][j] = dp[i-j][j] + dp[i][j-1];
                    }
                    
                }
            }
            cout<<dp[m][n]<<endl;

# 零钱兑换 #

## 题目描述 ##

> 想兑换100元钱，有1,2,5,10四种钱，问总共有多少兑换方法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 5][]

#include <iostream>
    #include <vector>
    using namespace std;
    const int moneys = 100;
    int coins[] = { 1,2,5,10 };
    
    //m 是剩余的钱，n 是剩余可选择的面值
    int getExchageTimes(int m, int n) {
    	//钱为0的情况
    	if (m == 0) return 1;
    	//不能兑换的情况
    	if (m < 0 || n <= 0) return 0;
    
    	//选择当前面值+不选择当前面值
    	return getExchageTimes(m - coins[n - 1], n) + getExchageTimes(m, n - 1);
    }
    const int N = 100;
    int arr[N + 1] = { 1 };
    int coinExchange(int n)   //非递归实现
    {
    	int i, j;
    	//i从0 ~ 3     因为每个arr[j]都要有一次是假设兑换了coins[i]，所以我们要遍历一次
    	for (i = 0; i < 4; i++)
    	{
    		for (j = coins[i]; j <= n; j++)
    			//求，arr[j]的时候，可以看出arr[j] = arr[j] + arr[j-coins[i]]，
    			//对应着上面的递归方式：arr[j]就是getExchageTimes(n, m-1)，
    			//arr[j-dimes[i]]就是getExchageTimes(n-coins[m-1], m)
    			arr[j] = arr[j] + arr[j - coins[i]];
    
    	}
    	return arr[n];
    }
    
    int main(void) {
    	int a[6] = { 1,2,3 };
    	//递归
    	cout << getExchageTimes(moneys,4) << endl;
    
    	//动态规划
    	cout << coinExchange(1) << endl;
    
    	return 0;
    }

参考文章：

[动态规划--换零钱][--]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221022/0aaf33c892c44b139611c5500c81cfc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1]: /images/20221022/9ac80a00651b48c8920aa5ae040eb96c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 2]: /images/20221022/d88edb63e2c347319ade2cf427fbcb28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 3]: /images/20221022/80c216e41dcb49929337c56662d00e42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 4]: /images/20221022/e7abfb556724496e89bf1ce05df872a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 5]: /images/20221022/5da6473ed6524fcf847d2b46795458e8.png
[--]: https://blog.csdn.net/callinglove/article/details/46421959