当前位置：首页 > news >正文

放苹果（动态规划问题/一点♥的思考）

news 2025/5/15 10:04:54

先看题目：

首先，这题我们直接明牌：动态规划

那接下来我们阐述思考过程。

我们一定学过或听说过斐波那契数列，斐波那契数列本质上就是一个动态规划。

所有我们有了一个心得认识，就是动态规划应该从小到大的一步步递进，也就是说我们应该先解决小问题，然后在小问题的基础上去解决大问题。

ok，接下来，我们定义一个动态规划数组dp[i][j],表示，将i个苹果放进j个盘子，基于对斐波那契数列的思考，我们就可以很容易接受，我们可以先从只有一个苹果/没有苹果等特殊情况，或者只有一个盘子甚至没有盘子等特殊情况展开，后序的更复杂的情况基于这些特殊情况。

我们之前说过，动态规划的话一定在创建动态规划数组后进行初始化，那基于上述的分析，我们就完全可以利用特殊情况进行初始化，斐波那契数列的前几个元素何尝不是一种特殊的初始化？

那我们就可以看一下我们的初始化代码：

for(int i=0;i<=m;i++) // 只有一个盘子
{dp[i][1] = 1;
}for(int j=0;j<=n;j++) // 没有苹果
{dp[0][j] = 1;
}

其实非常好理解的，我们对于上述的特殊情况的初始化就不再详细阐述，只是要特别记住，dp[i][j]的含义是i个苹果，放入j个盘子，那上述初始化你一定可以理解。

好了，初始化完成后我们就一定需要去找状态转移方程，说的简单点就是后面的动态规划是怎么基于前面情况展开的。

首先，我们肯定是要两层循环的，那我们就不可避免地是j>i，也就是说盘子地个数会大于苹果地个数，这种情况下，i个苹果在j个盘子地情况就可以等价于在在i个盘子地情况，j-i个盘子怎么都是空的。

那另一种就是苹果的个数大于盘子地个数。这又会分成两种情况，一个是每个盘子至少一个苹果，另一个是至少一个盘子是空的，对于第一种情况，那我们可以提前往每个盘子里先放一个苹果，也就是dp[i][j] = dp[i-j][j]，对于第二种情况，至少一个盘子是空的，那就是dp[i][j-1]（对于至少地处理我也有点不是特别明白，可能是只有一个盘子是空的这个值最大），最后分出的两种小情况要相加。

我们继续看代码：

	for(int i=1;i<=m;i++){for(int j=2;j<=n;j++){if(i<j){dp[i][j] = dp[i][i]; // 苹果的个数小于盘子的个数}else{dp[i][j] = dp[i][j-1]+dp[i-j][j]; // 苹果的个数大于盘子个数还有两种情况// 一个是至少一个盘子空，另一个是每个盘子至少一个苹果}}}

还有一个需要注意的是，i为0以及j为1/2的情况我们在特殊情况里面已经讨论过了，这里就不能在继续对其处理，否则就会类似于操作自己然后处理自己，是不合适的。

那最后我们只需要输出dp[m][n],m个苹果放n个盘子的情况。

所有总的代码就是：

// 放苹果
# include<iostream>
# include<vector>
# include<algorithm>
# include<iomanip>
using namespace std;int main()
{int m,n;cin>>m>>n;// dp[i][j]代表什么，表示i个苹果放入j个盘子的方法个数// 化大为小// 初始化找特殊情况vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=0;i<=m;i++) // 只有一个盘子{dp[i][1] = 1;}for(int j=0;j<=n;j++) // 没有苹果{dp[0][j] = 1;}for(int i=1;i<=m;i++){for(int j=2;j<=n;j++){if(i<j){dp[i][j] = dp[i][i]; // 苹果的个数小于盘子的个数}else{dp[i][j] = dp[i][j-1]+dp[i-j][j]; // 苹果的个数大于盘子个数还有两种情况// 一个是至少一个盘子空，另一个是每个盘子至少一个苹果}}}cout<<dp[m][n]<<endl;return 0;
}

ok，就到这里，把案例还有同学没走，那我再等一下，查一查那个问题。

是这样说的

dp[i][j - 1]表示的是通过“强制减少一个盘子”来覆盖所有“至少一个空盘”的情况，利用了盘子相同的性质，避免了重复计数。这是动态规划中状态转移的核心思想之一。