用洛谷和力按钮解决动态规划问题，总是想破脑袋也想不出状态转移方程式是怎么写的。 看答案很多人在写。 从这个时候开始怀疑自己的智商。 不能给出简单问题的动态迁移方程。 最近看了zjdxd的说明，明白了这其中存在道路。
示例：如果您有一个硬币面值数组arr，例如[ 100，24，35，76，50 ]，并询问有多种组合方法使合计达到目标值，则会给出另一个目标值，例如1000。
接下来，我们将一步一步地说明暴力递归是如何转变为动态计划的。1.暴力递归基本思路:首先，用编号index表示可变参数是什么，需要找到所有可变参数，主题可变参数选择了哪个面额的钱，剩下的目标值需要用rest表示函数process(index，rest )表示从编号index到达rest有多种方法，在主函数中调用process (0，1000 )表示。 代码如下。
intprocess1(intindex，int rest ) if (rest0) { return 0； }if(index==num ) (如果index达到最后一个面值，是否确定当前rest是否为0 return rest==0？ 1:0； (} int ways=0； for (int张=0； 张* arr [索引]=rest； 张() ways=process1(索引1，rest -张* arr [索引] )； //解开空间树的横向扫描}返回方向； (}int way1) ) intRES=process1(0，target )； coutresendl； } 2.将暴力递归改为记忆化搜索简言之，将return的返回值更新为dp数组
int dp[MAX][MAX]； //如果可变参数数组的初始化值为-1，则表示我从来没有遇到过这种情况，void init () for ) inti=0； iMAX； I ) for(intj=0； jMAX； j({DP[I][j]=-1； }}intprocess2(intindex，int rest ) (/内存化搜索前代码return的返回值DPif(DP[index][rest]！=-1 ) { return dp[index][rest]； //如果以前出现过，但仍然(if(index==num ) index达到最后一个面额，则确定当前rest是否为0 dp[index][rest]=rest==0。 1:0； return DP [索引] [ rest ]； //return rest==0？ 1:0； (} int ways=0； for (int张=0； 张* arr [索引]=rest； 张() ways=process1(索引1，rest -张* arr [索引] )； //清除空间树的横向扫描(} DP [索引] [ rest ]=ways； return DP [索引] [ rest ]； (}int way2) ) { init )； //初始化函数intres=process2(0，target )； coutresendl； } 3.将记忆化搜索改完动态规划
int dp2[MAX][MAX]； int process3(()//动态规划或保持上面的代码不变，dp2[num][0]=1； for(intindex=num-1； 索引=0； 索引----} { for (intrest=0； rest=target； rest({intways=0； for (int张=0； 张* arr [索引]=rest； 张) { ways=dp2 [ index1] [ rest -张* arr [ index ]； //将暴力递归调用的函数转换为dp } dp2[index][rest]=ways； } } return dp2[0][target]； }void way3() { int res=process3)； coutresendl； } 4.进一步优化动态规划
如图所示，假设您来到当前面额为3、索引为10的单元。
格，在同一层可以发现也存在重复计算，右边的那个值可以从左边和下边来，于是得到转移方程：dp[index][rest] = dp[index][rest-arr[index]]+dp[index+1][rest]如果rest-arr[index]>=0。很多题解直接给出这个方程，其实他们也是这么过来的，但是麻烦就不会告诉你这么去想 int dp3[MAX][MAX];int process4(){ //动态规划，还是照着上面的代码进行修改 dp3[num][0]=1; for(int index=num-1;index>=0;index--) { for(int rest=0;rest<=target;rest++) { dp3[index][rest]= dp3[index+1][rest]; if(rest-arr[index]>=0) { dp3[index][rest]+=dp3[index][rest-arr[index]];//把暴力递归调用的函数换成dp } } } return dp3[0][target];}void way4(){ int res = process4(); cout<<res<<endl;}全部代码如下：
#include<bits/stdc++.h>#define MAX 100using namespace std;int arr[MAX];int num;//输入数组int target;int process1(int index,int rest){ if(index == num) { //如果index来到最后一个面值，判断当前的rest是否等于0 return rest ==0?1:0; } int ways=0; for(int zhang=0;zhang*arr[index]<=rest;zhang++) { ways+=process1(index+1,rest-zhang*arr[index]);//解空间树横向扫描 } return ways;}void way1(){ int res = process1(0,target); cout<<res<<endl;}int dp[MAX][MAX];//可变参数数组初始化值为-1表示我之前还没有遇到过这种情况void init(){ for(int i=0;i<MAX;i++) { for(int j=0;j<MAX;j++) { dp[i][j]=-1; } }}int process2(int index,int rest){ //记忆化搜索 上一个代码return的返回值更新dp if(dp[index][rest]!=-1) { return dp[index][rest];//以前出现过，直接返回 } if(index == num) { //如果index来到最后一个面值，判断当前的rest是否等于0 dp[index][rest] = rest==0?1:0; return dp[index][rest]; //return rest ==0?1:0; } int ways=0; for(int zhang=0;zhang*arr[index]<=rest;zhang++) { ways+=process1(index+1,rest-zhang*arr[index]);//解空间树横向扫描 } dp[index][rest] = ways; return dp[index][rest];}void way2(){ init();//初始化函数 int res = process2(0,target); cout<<res<<endl;}int dp2[MAX][MAX];int process3(){ //动态规划，还是照着上面的代码进行修改 dp2[num][0]=1; for(int index=num-1;index>=0;index--) { for(int rest=0;rest<=target;rest++) { int ways=0; for(int zhang=0;zhang*arr[index]<=rest;zhang++) { ways+=dp2[index+1][rest-zhang*arr[index]];//把暴力递归调用的函数换成dp } dp2[index][rest]=ways; } } return dp2[0][target];}void way3(){ int res = process3(); cout<<res<<endl;}int dp3[MAX][MAX];int process4(){ //动态规划，还是照着上面的代码进行修改 dp3[num][0]=1; for(int index=num-1;index>=0;index--) { for(int rest=0;rest<=target;rest++) { dp3[index][rest]= dp3[index+1][rest]; if(rest-arr[index]>=0) { dp3[index][rest]+=dp3[index][rest-arr[index]];//把暴力递归调用的函数换成dp } } } return dp3[0][target];}void way4(){ int res = process4(); cout<<res<<endl;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>num>>target; for(int i=0;i<num;i++) { cin>>arr[i]; } way1();//暴力递归 way2();//记忆化搜索 way3();//动态规划 way4();//动态规划优化 return 0;}测试结果: