动态规划——矩阵问题_有一个5x4的矩阵,从左上角的格子开始每次只能向右或者向下走,最后到达右下角

题目

给定一个矩阵arr，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有数字累加起来就是路径和，返回所有路径中最小路径和，如果给定的arr如大家看到的样子，路径1，3，1，0，6，1，0就是路径中和最小的，所以返回12。

//矩阵arr
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0 

思路

生成大小和arr一样的矩阵dp，dp[i][j]的值表示从左上角，也就是(0,0)位置，走到(i,j)位置的最小路径和。
dp第一行的值就是arr第一行的值不断累加的结果。
dp第一列的值就是arr第一列的值不断累加的结果。
dp[i][j]=arr[i][j]+min(dp[i-1][j],dp[i][j-1])

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
 
int arr[4][4]=
{
	{1,3,5,9},
	{8,1,3,4},
	{5,0,6,1},
	{8,8,4,0}
};
 
int minStep(int row,int col,int dp[][4])
{
	int s1,s2;
	for(int i=0;i<row;++i)
	{
		for(int j=0;j<col;++j)
		{
			int s1=1000;
			int s2=1000;
			if(i==0&&j==0)
			{
				dp[i][j]=1;
				continue;
			}
			else if(i==0&&j==1)
			{
				dp[i][j]=4;
				continue;
			}
			else if(i==1&&j==0)
			{
				dp[i][j]=9;
				continue;
			}
			//向上，向左
			if(i-1>=0)
				s1=dp[i-1][j]+arr[i][j];
			if(j-1>=0)
				s2=dp[i][j-1]+arr[i][j];
			dp[i][j]=min(s1,s2);
		}
	}
	return dp[row-1][col-1];
}
int main()
{	int row,col;
	int dp[4][4]={1000};
	row=4;
	col=4;
	cout<<minStep(row,col,dp)<<endl;
 
	system("pause");
	return 0;
}