猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中,精灵鼠从(0,0)的位置进入建筑群,建筑群的出口位置为(n-1,n-1),建筑群的每个位置都有阻碍,每个位置上都会相当于给了精灵鼠一个固定值减速,因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑,现在问精灵鼠最少在减速多少的情况下逃出迷宫?
输入描述:
第一行迷宫的大小: n >=2 & n <= 10000;
第2到n+1行,每行输入为以','分割的该位置的减速,减速f >=1 & f < 10。
输出描述:
精灵鼠从入口到出口的最少减少速度?
示例1
输入
3
5,5,7
6,7,8
2,2,4
输出
19
解题思路:精灵鼠第<i,j>个状态第<i - 1,j>(上)和第<i,j - 1>(左)得来,要求求出最小减速度,故取第<i - 1,j>(上)和第<i,j - 1>(左)两个状态中的最小值,动态规划方程为:dp[i][j] = min(dp[i - 1][j],dp[i][j - 1])
注意点: i = 0时,dp[i][j] = dp[i][j - 1]
j = 0时,dp[i][j] = dp[i - 1][j]

#include<iostream>
using namespace std;
int map[10005][10005];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d%c",&map[i][j]);
        }
    }
    //dp[i] = min(dp[i - 1][j],dp[i[j - 1]])
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == 1){
                map[i][j] += map[i][j - 1];
            }else if(j == 1){
                map[i][j] += map[i - 1][j];
            }else
                map[i][j] += min(map[i - 1][j],map[i][j - 1]);
        }
    }
    cout << map[n][n] << endl;
    return 0;
}