矩阵最小路径和 动态规划

Description

 给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。编写一个实验程序求所有路径和中的最小路径和。例如，以下矩阵中的路径1->3->1->0->6->1->0是所有路径中路径和最小的，返回结果是12：

 

1  3  5  9
8  1  3  4
5  0  6  1
8  8  4  0

#include 
#include 
#include 
#include 
using namespace std;








int main()
{
    int m,n;
    cin>>m>>n;
    int a[m][n];
    int dp[m][n];
    for(int i=0;i){
        for(int j=0;j){
            cin>>a[i][j];
        }
    }
    dp[0][0]=a[0][0];
    

    for(int i=1;i//第一列 
        dp[i][0]=dp[i-1][0]+a[i][0];
    }
    for(int j=1;j//第一行 
        dp[0][j]=dp[0][j-1]+a[0][j];
    }
    for(int i=1;i){
        for(int j=1;j){
            if(dp[i-1][j]>dp[i][j-1]){
                dp[i][j]=dp[i][j-1]+a[i][j];
            }else{
                dp[i][j]=dp[i-1][j]+a[i][j];
            }
            
            
        }
    }
cout<1][n-1];
    return 0;
}
算法设计与分析

相关

算法设计与分析

算法设计与分析——背包问题求解

算法设计与分析——简答概述

算法设计与分析「通关指南」

标签