秒懂百科，C++如此简单丨第十九天：动态规划

目录

动态规划的初步理解

求最短路径数

洛谷 P1002 过河卒 

题目描述

输入样例

输出样例 

思路

AC Code

Everyday English

The greatest glory in living lies not in never falling, but in rising every time we fall.

生命中最大的荣耀不在于从未跌倒，而在于每次跌倒后都能重新站起来。

动态规划的初步理解

什么是动态规划？最直白的理解就是动态的规划。

那高级一点的理解呢？就是每时每刻都拿着一个小本本，也就是记事本，把干的事情都记录下来，不断规划自己的策略，这就是动态规划。

动态规划里的小本本就对应着程序里的数组，而策略不就是往里依次填值吗。

动态规划理解到这，恭喜你，你已经了解了动态规划了。简单吧！

那我们边讲题，边理解！

动态规划我们一般用dp来表示。

求最短路径数

问从A（1,1）走到B（n,m）有几种最短路径（每次只能向相邻的格子走一格）？

要求：输入B的行坐标(n)和列坐标(m)，输出最短路径总数

这题咋一看，毫无头绪，是嵌套for循环？还是while？都不是，是DP，你看：

假设输入的是2和3，那么先把格子画出来，是这样的。

那每个格子里该填什么呢？对了，应该填到当前格子的最短路径数。那是不是每个格子都要从头输一遍呢？你仔细想想，题目说要最短，那走回头路肯定不行，那只能往下走或者右走，这样才能确保最短。因此每一格的最短路径数，不就是它上面的格子+左边的格子吗？

知道了DP公式，那好做了。

填完就是这样的，你可以验证一下：

最后输出dp[n][m]就完事了，上代码：

#include
using namespace std;
int main()
{
	int n,m,dp[505][505];
	memset(dp,0,sizeof(dp)); 
	cin>>n>>m;
	for(int i=1;ix>>y;
    n+=1;m+=1;x+=1;y+=1;
    for(int i=0;i=1&&nx=1&&ny