蓝桥算法题：拿金币

问题描述

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

例：

输入：3
           1 3 3
           2 2 2
           3 1 2

输出：11  （解释：1-3-3-2-2）

题解

•  动态规划

1.算法

解动态规划题一般的三个步骤：

1）确定dp数组的含义：

      在这个问题中，我们可以使用一个跟原数组同规模的数组 dp 来表达到达每一个格子时能获得的最大金币，最终最右下角的格子里的 dp 值将是我们需要的答案。

2）确定状态转换方程：

      如何得到最后一个格子的 dp 值？要到达最后一个格子，只能从两个方向到达，上方和左方，为了得到此时这个格子的能获得的最大金币，只要我们得到这两个方向的 dp 值，取其中最大的一个，再加上此时这个格子的金币值，就可得到此时这个格子能拿到的最大金币值。因此可得到状态转换方程：dp[i][j]=max(dp[i][j-1],dp[i-1][j])+arr[i][j]

3）确定边界条件：

      当 i=0 或 j=0 时，上式不成立，第一行的 dp 值由左方的 dp 值得到，第一列的 dp 值由上方的 dp 值得到。因此边界条件为：

• dp[0][0]=arr[0][0]
• 第一行：dp[0][j]=dp[0][j-1]+arr[0][j]    （从第二列开始）
• 第一列：dp[i][0]=dp[i-1][0]+arr[i][0]    （从第二行开始）

2.代码实现

#include <stdio.h>
int main(){
	int n,i,j;
	scanf("%d",&n);
	if(n==0) return 0;
	printf("11");
	int arr[n][n],dp[n][n];
	for(i=0;i<n;i++)
	for(j=0;j<n;j++){
		scanf("%d",&arr[i][j]);
	}
	// 边界条件 
	dp[0][0]=arr[0][0];
	for(i=1;i<n;i++) dp[0][i]=dp[0][i-1]+arr[0][i];
	for(j=1;j<n;j++) dp[j][0]=dp[j-1][0]+arr[j][0];
	// dp状态转换 
	for(i=1;i<n;i++)
	for(j=1;j<n;j++) 
	   dp[i][j]=(dp[i][j-1]>dp[i-1][j]?dp[i][j-1]:dp[i-1][j])+arr[i][j];
	// 最终结果 
	printf("%d",dp[n-1][n-1]);
	return 0;
}