学习目标：

每天睡前是否感到浑浑噩噩，一天又在不知不觉中过去，回想我今天都干了什么呢？

啊~我这一天又什么也没干，好有罪恶感啊，不行，我明天一定要好好学算法（手动狗头）。

明日复明日，明日何其多？不要等明天啦，和小编一起，每天睡前一道算法题，不仅解决你一天的空虚，更能助你安心入眠，远离熬夜。还能学到一点算法知识。不要小看这些知识哦，不积跬步无以至千里，不积小流无以成江海。每位大佬都不是一夜成名，都是从小白做起，日积月累，终成大佬，和小编一起，每日一题，走向大佬之路吧！

学习内容：

熟悉小编的写作风格的朋友都知道，小编喜欢“见一叶而知秋”，从一道题目中看出它所蕴涵的思想，学习的是这种思想，然后再反作用于题目。这样不仅能学会这一道题，更能学会这一类题，也就是我们常说的“授人之鱼不如授之于渔”。希望每位朋友看完后，学会的不仅是题目，更是其中蕴含的思想。

?我们今天的题目是蓝桥杯中的一道题——找金币。归类是动态规划，简称DP。

让我们先看一下题目：

问题描述

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

输入格式

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

输出格式

　　最多能拿金币数量。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

数据规模和约定

　　n<=1000

看完题目没有思路不要紧，让我们先来看一下它的原理——动态规划。

如果你从未接触过动态规划，那么和小编一起来了解下吧！

什么是动态规划？

简单来说，就是利用历史记录来避免重复计算。举个栗子🌰，我们通常求解斐波那契数列（F（n）=F（n-1）+F（n-2））的时候，应用的是递归的方法。

int f(int n){
	if(n==0 || n==1) return 1;
	return f(n-1)+f(n-2);
}

但是当我们要求f（100）+f（99）的时候，在求解f（100）的过程要经过求f（99），但是求f（99）的时候还需要重新计算，也就是我们的历史记录没有被利用，那么会造成相同的过程要重复计算。那么如何避免这种情况呢？

我们可以通过数组记录每一个f（n）的值，那么当我们需要再次使用时，就可以直接从数组中进行调用了。而这个用数组存储历史记录的方法，就称作动态规划。

#define ans 1000
int num[ans];
int f(int n){
	num[0]=num[1]=1;
	int i=2;
	while(i<=n){
		num[i]=num[i-1]+num[i-2];
		i++;
	}
	return num[n];
}

在对动态规划有了初步的了解后，小编喜欢给大家上干货：动态规划的一般步骤：

第一步：定义数组元素含义：

我们通常定义一个数组dp来保存历史数据，但是这些数据的意义是什么？以上述为例，我们的数组元素的含义是第i个斐波那契数的数值为num[i]。而我们动态规划的过程中更多会遇到的是二维数组。

第二步：找出数组元素之间的关系：

这一步就像我们曾经学过的归纳法，找关系。上述的关系就是f（n）=f（n-1）+f（n-2）。这一步也就是我们动态规划的核心。

第三步：找出数组的初始元素值：

通过第二步我们能够找到元素之间的关系，但是只有关系还不足以确定整个数组的值，我们需要从后往前进行归纳，一直到最开始的那个基本元素。上述的初始值就是n=0和n=1的值，需要我们规定为1。

有了初始值和关系式之后，我们就能得到整个dp数组的值了。

知道了动态规划以后，让我们回顾刚才的题目。是比斐波那契多了一维，并且我们遇到的90%的题基本都是要二维的，但是总的思路是不变的。让我们按照模板一起来看看：

第一步：数组元素含义，dp[i][j],表示第i行j列位置能获得的最大金币数。

第二步：数组元素间的关系，每一步只能向下或者向右走一步，那么dp[i][j]位置只能是通过dp[i-1][j]或dp[i][j-1]移动得到，那么dp[i][j]的最大值取max（dp[i-1][j]，dp[i][j-1]）+num[i][j]。关系表达式也就是dp[i][j]=max（dp[i-1][j]，dp[i][j-1]）+num[i][j]；

第三步：数组的初始值，数组的初始值在于数组的左边界和上边界，他们只能由前一个数加num[i][j]得到。所以对他们进行初始化。

dp[0][0]=num[0][0];
	for(i=1;i<n;i++){
		dp[i][0]=dp[i-1][0]+num[i][0];
		dp[0][i]=dp[0][i-1]+num[0][i];
	}

注意！！！千万不要搞混dp数组和num数组！！！

dp是我们自行构造的数组，num是根据题意的输入数组。

最后让我们看一下代码如何实现：

#include<stdio.h>
int max(int a,int b){
	return a>b?a:b;
}
int main() {
	int n,i,j;
	scanf("%d",&n);
	int num[n][n],dp[n][n];
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%d",&num[i][j]);
			dp[i][j]=0;
		}
	}
	dp[0][0]=num[0][0];
	for(i=1;i<n;i++){
		dp[i][0]=dp[i-1][0]+num[i][0];
		dp[0][i]=dp[0][i-1]+num[0][i];
	}
	for(i=1;i<n;i++){
		for(j=1;j<n;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+num[i][j];
		}
	}
	printf("%d",dp[n-1][n-1]);
	return 0;
}

虽然不说，但相信clever的你一定不会忘记留下你的点赞和关注，也要记得收藏，防止找不到哦！

欢迎大家订阅小编的每日一题专栏，会每天更新，都是用心准备的哦！

若有不同思路，欢迎评论区留言，看到必回，Goodnight！