动态规划练习（2）拿金币

￡神魔★判官ぃ 2023-09-28 15:28 20阅读 0赞

### **问题描述** ###

有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式

第一行输入一个正整数n。  
　　以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式

最多能拿金币数量。

样例输入

3  
1 3 3  
2 2 2  
3 1 2

样例输出

数据规模和约定

n<=1000

**架子摆起，开整**

四大步骤：

一：确定状态

*  最后一步
 *  化成子问题

二：状态转移

*  写出表达式

三：初始条件和边界情况

四：计算顺序

**分析：**

**表格嘛，得用二维数组（因为要二维坐标才能表示嘛）， 大小为输入的 n+1，设为dp\[i\]\[j\]表示到坐标（i，j) 最多能拿的金币数量, 再用个二维数组Au\[n+1\]\[n+1\]用来保存每个格子里的金币数量。**

**一：确定状态**

最后一步：只能是向下到达，即从坐标（n-1,n）到（n,n），得金币

dp\[n\]\[n\]=dp\[n-1\]\[n\]+Au\[n\]\[n\]

或者向右到达，即从坐标（n,n-1）到（n,n），得金币

dp\[n\]\[n\]=dp\[n\]\[n-1\]+Au\[n\]\[n\]

化子问题：求到坐标（ i , j ）(1<= i,j <=n)最多能拿的金币数量？

向下到达时：**dp\[i\]\[j\]=dp\[i-1\]\[i\]+Au\[i\]\[i\]**

向右到达时：**dp\[i\]\[j\]=dp\[i\]\[i-1\]+Au\[i\]\[i\]**

**二：状态转移**

dp\[i\]\[j\] = **max(** dp\[i-1\]\[i\] , dp\[i\]\[i-1\] **)** \+ Au\[i\]\[i\]

（或者dp\[i\]\[j\] = **max(** dp\[i-1\]\[i\]+ Au\[i\]\[i\] , dp\[i\]\[i-1\] + Au\[i\]\[i\]**)** 也行）

**三：初始条件和边界情况**

初始条件：当i==0或者j==0,时dp\[i\]\[j\] =0,当i==1或者j==1时，由于i-1行和j-1列均不存在了，求的又是获得最大金币数，所以可以设 第 0 行和第 0 列的金币数为0

边界情况：貌似没有边界限制，一切都由n定，1到n之间所有值均满足状态转移方程

**第四步：计算顺序**

从已知向未知方向出发，已知当i==0或者j==0,时dp\[i\]\[j\] =0;未知dp\[n\]\[n\],所以for循环顺序 i 和 j均是从1到n。

### **分析完毕** ###

#include<iostream>
    using namespace std;	
    int main(){
    	int n,i,j;
    	cin>>n;
    	int dp[n+1][n+1],Au[n+1][n+1];
    	
    	for(i=1; i<=n; i++)
    		for(j=1; j<=n; j++){
    			cin>>Au[i][j];  //赋初值 
    			dp[0][j]=dp[j][0]=0; //顺便初始化 
    		}
    		
    	for(i=1; i<=n; i++)
    		for(j=1; j<=n; j++)
    		    dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + Au[i][j]; 
    		    
    	cout<<dp[n][n];					
    	return 0;
    }

![65efd17dfd5746758624ab75ed76fe15.png][]

![508032c97d2645d999da27627ccb7ea4.png][]

## 总结 ##

1、不知道用几维数组，那就直接用二维，写着写着就知道了，如果写到一半发现根本用不着第二维的下表，那接下来直接写一维呗，但如果一开始用的一维数组，一旦用错了就会发现根本写不下去了，必须得从头再来，麻烦且费时。

2、化子问题那一小步或许可能省略不写脑袋想想就行了，但状态转移方程一定一定一定必须写出来！！！！绝对不能偷懒，因为你不知道最后一步情况判断完了没有，也不知道构造的状态方程对不对，一旦哪地方错了，绝对能卡你半小时以上，所以这一步绝对不能偷懒

3、构成最后一步的情况一定要想全，有时候可能一次并不能想全，只能对一半，那很有可能是还有情况没考虑到。

3、嗯~！~~~~~，敲代码不能急，要稳当些，着急是一个大忌，把 j 敲成 i 你看看能不能卡死你。

4、还没领悟，嘿嘿

[65efd17dfd5746758624ab75ed76fe15.png]: https://img-blog.csdnimg.cn/65efd17dfd5746758624ab75ed76fe15.png
[508032c97d2645d999da27627ccb7ea4.png]: https://img-blog.csdnimg.cn/508032c97d2645d999da27627ccb7ea4.png