文章目錄

• 題目描述
• 題解
• 思路1 暴力遞歸
• 思路2：緩存思想——?jiǎng)討B(tài)規(guī)劃來優(yōu)化暴力遞歸

題目描述

鏈接：點(diǎn)我做題

題解

思路1 暴力遞歸

??我們利用遞歸來解決這個(gè)問題，不妨這樣思考，假設(shè)apples表示當(dāng)前剩余的蘋果數(shù)，plates表示當(dāng)前剩余的盤子數(shù)，ways(apples, plates)表示以apples個(gè)蘋果放進(jìn)plates個(gè)盤子里的方法數(shù)。
??如果apples==0，說明當(dāng)前蘋果都已經(jīng)放完了，既然放完了，不管剩不剩盤子，這都是一種放的方法，向上一層返回1；
??否則apples不為0的時(shí)候，如果plates==0了，盤子已經(jīng)被用完了但是蘋果沒放完，這種情況顯然是擺放失敗了，不是一種擺放的方法，向上一層返回0;
??再考慮一種特殊情況，當(dāng)盤子數(shù)大于蘋果數(shù)時(shí)，那么蘋果怎樣也不可能放到多出來的盤子上，這種情況下的擺放方法數(shù)顯然和盤子減少為$plates?apples$個(gè)，apples個(gè)蘋果的擺放方法數(shù)是一樣多的，因此
$$\begin{gathered} if(apples<plates), \\ ways(apples,plates)=ways(apples,plates?apples) \end{gathered}$$
??當(dāng)剩余的蘋果數(shù)量大于盤子數(shù)量時(shí)，我們有兩種互斥的擺法：
??一種，我們用上所有的盤子,也就是先讓所有的盤子都擺上一個(gè)蘋果，那么這種方式的擺法數(shù)量a顯然等于$ways(apples?plates,plates)$;
??另一種方法，我們不用上所有的盤子，那么怎么才能不用上所有的盤子呢？先放棄一個(gè)盤子，剩下的盤子是放棄還是保留交給遞歸來討論。也就是說，不完全使用所有盤子的擺放方法數(shù)量b等于$ways(apples,plates?1)$.
??這兩種情況顯然是互斥的，所以他們的方法數(shù)可以直接相加，也就是說
$$\begin{gathered} if(apples>plates) \\ ways(apples,plates)=ways(apples?plates,plates) \\ +ways(apples,plates?1) \end{gathered}$$
代碼：

int ways(int apples, int plates) {//apples個(gè)完全相同的蘋果放到plates個(gè)完全相同的盤子里//有多少種方法//如果蘋果用完了 說明擺放結(jié)束了 返回一種擺法if (apples == 0) {return 1;}//如果plates等于0了 apples不等于0還 那么說明沒有盤子用了//0種擺法if (plates == 0) {return 0;}//如果盤子數(shù)大于蘋果數(shù) 那么多出來的盤子不論什么擺法一定空著//這種情況下的擺法數(shù)等于把多出來的盤子都不考慮的擺法數(shù)if (plates > apples) {return ways(apples, apples);}//當(dāng)蘋果數(shù)大于盤子數(shù)的時(shí)候 有兩種方法//1) 我們把所有的盤子都使用 那么相當(dāng)于先往所有盤子上都放一個(gè)蘋果// 這種方法的方法數(shù)等于ways(apples - plates, plates)int a = ways(apples - plates, plates);//2) 我們讓盤子不全都使用 那么就敲碎一個(gè)盤子 //剩下的盤子全用還是敲碎一個(gè) 總可能方法數(shù)用遞歸去討論int b = ways(apples, plates - 1);//這兩種情況顯然是互斥的 所以數(shù)量可以直接加return a + b; }

思路2：緩存思想——?jiǎng)討B(tài)規(guī)劃來優(yōu)化暴力遞歸

??所有的暴力遞歸的展開過程都可以用動(dòng)態(tài)規(guī)劃來優(yōu)化.我們想想遞歸是怎么解決問題的，比如遇到ways(7, 5)，它是展開為ways(7,4)和ways(2,5)來解決的，然后ways(2,5)和ways(7,4)再接著展開，那如果我們之前早就計(jì)算過ways(2,5)了呢,如果已經(jīng)計(jì)算過一次了，還有必要再接著展開嗎？直接用上次計(jì)算的結(jié)果不就好了，這樣不就可以把遞歸層數(shù)變淺了嗎。
??那么怎么記錄上次計(jì)算的結(jié)果呢？這里可以用一個(gè)二維數(shù)組dp緩存存起來，并且考慮到多組輸入問題，我們可以把創(chuàng)建二維數(shù)組dp的過程放到執(zhí)行ways方法外頭，這樣下一組輸入也可以使用我們上一輪計(jì)算過的值。
??為了和0種方法區(qū)分，我們不妨先讓dp的所有值都賦-1，表示尚未計(jì)算過，在遞歸的每一層都檢查當(dāng)前層中dp的是否不等于-1，如果是，說明這層沒必要繼續(xù)展開下去了，已經(jīng)計(jì)算過了，返回$dp[apples][plates]$,否則再執(zhí)行展開過程，并且最后把這一層的計(jì)算結(jié)果記錄到dp中作為緩存。

代碼：

#include <vector> #include <iostream> using namespace std; int ways(int apples, int plates, vector<vector<int>>& dp) {if (dp[apples][plates] != -1){return dp[apples][plates];}int ans = 0;if (apples == 0){ans = 1;}else if (plates == 0){ans = 0;}else if (apples < plates){ans = ways(apples, apples, dp);}else{int a = ways(apples - plates, plates, dp);int b = ways(apples, plates - 1, dp);ans = a + b;}dp[apples][plates] = ans;return ans; }int main() {int apples, plates;vector<vector<int>> dp(11, vector<int>(11, -1));while (cin >> apples >> plates){cout << ways(apples, plates, dp) << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的算法题放苹果：把M个相同的苹果放到N个完全相同的盘子里，有多少种放法?的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。