今天运用所学完成了一道简单的动态规划题
思路:1、仅能向右或向下走，这意味着行走过程是从左到右，从上到下有序
? ? ? ? 2、我们假设已知结果，(实质是从右向左推)例如，要想到达行 2 列 2，我们必须经过行 1 列 2 或行 2 列 1，则假设我们知道，要求到达行 2 列 2 的最短时间必定是 行 2 列 2 所需行走时间 + 上 行 1 列 2 或 行 2 列 1（选最小）。
? ? ? ? 3、知道了我们求解的思想后，我们设到达各个方格总共所需的最小时间记录在 dp[] 数组内，推导出公式：dp[i][j] = Min( dp[i][j - 1], dp[i -1][j]) + arr[i][j] (其中arr[] 为走过各个单一方格所需的时间，(如果没理解等会代码可看看)。
????????
#include<iostream>
#include<cmath>?
#include<cstring>
#define INF 9999999? ? //设置一个极大数值非常重要
using namespace std;
int main()
{
?? ?int row, column;
?? ?while(cin>> row>> column){
?? ??? ?int arr[row + 1][column + 1];
?? ??? ?int i, j;
?? ??? ?
?? ??? ?for(i = 1; i <= row; i ++)
?? ??? ??? ?for(j = 1; j <= column; j ++){
?? ??? ??? ??? ?cin>> arr[i][j];? ? ?//把通过单一方格所需的时间记录在里面
?? ??? ??? ?}
//-------------------------------------?? ?初始化?? ??? ?
?? ??? ?int dp[row + 1][column + 1];? ?//记录总时间
?? ??? ?memset(dp, 0, sizeof(dp));
?? ??? ?
?? ??? ?for(i = 0; i <= row; i ++){
?? ??? ??? ?dp[i][0] = INF;
?? ??? ?}
?? ??? ?for(i = 0; i <= column; i ++){
?? ??? ??? ?dp[0][i] = INF;
?? ??? ?}
?? ??? ?dp[1][0] = dp[0][1] = 0;
//--------------------------------------------
// 简单的二维数组动态规划? ? ? ??
?? ??? ?for(i = 1; i <= row; i ++)
?? ??? ??? ?for(j = 1; j <= column; j++){
?? ??? ??? ??? ?dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
?? ??? ??? ?}?? ?
?? ??? ?for(i = 1; i <= row; i ++){? //输出所有位置所需最短时间
?? ??? ??? ?for(j = 1; j <= column; j++){
? ? ? ? ? ? ? ? cout<< dp[i][j]<<' ';? ?
? ? ? ? cout<< endl;
? ? ? ? }? ? ??
?? ?}
?? ?return 0;
}
4、最初我没有设置 INF 来覆盖 0 行的方格 和 0 列的方格，就只能单一的给第一列和第一行单独赋值，有些麻烦，如果灵活利用 数组下标为0的位置，把第0列和第0行设为极大值，即可简单便捷的完成任务，也方便理解。
