LeetCode-Minimum Path Sumの二次元配列の最小経路、ダイナミック企画

これは一連のダイナミック企画のアルゴリズムであると感じています.
アルゴリズム1:
重み付きの最小パスの問題
Given a m x n grid filled with non-negative numbers、find a path from top left to bottom right which minimizes the sum of all numbers along its path.
まず、各パスの前のパスはその上と左から来ます.
一番上のパスを合計して、一番左のパスを求めます.(ここで直接的に和を求めることができないのは、一次元配列res[n]でパスを記録します.ここでは空間をうまく節約します.だから、一番左の求和アルゴリズムを循環の中に入れました. res[i][j]=min(res[i-1][j],res[i]、[j-1]+val[i][j] )

class Solution {
public:
    int minPathSum(vector > &grid) {
        if(grid.empty() || grid[0].empty())
        {
            return 0;
        }
        int m = grid.size();
        int n = grid[0].size();
        int *res = new int[n];
        res[0] = grid[0][0];
        for(int i = 1;i < n; i++)
        {
            res[i] = res[i-1]+grid[0][i];
        }
        for(int i = 1; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if (0 == j)
                {
                    res[j] += grid[i][0];
                }
                else
                {
                    res[j] = min(res[j-1],res[j])+grid[i][j];
                }
                
            }
        }
        int result = res[n-1];
        delete []res;
        return result;
    }
};

このようなダイナミック企画と似たアルゴリズムがあります.
Unique Paths
 
https://leetcode.com/problems/unique-paths/
A robot is located the top-left coner of a m x n grid(marked'Start'in the diagram below)
The robot can only move eigner down or right at any point in time.The robot is trying to reach the bottom-right Coner of the grid.
How many possible unique paths are there?
Above is a 3 x 7 grid.How many possible unique paths are there?
ノート: m and n will be at most 100.

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m == 0 || n == 0)
        {
            return 0;
        }
        int res[100][100];
        for(int i = 0; i < n; i++)
        {
            res[0][i] = 1; //

一次元空間のみを利用する場合:

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m <= 0 || n <= 0
        {
            return 0;
        }
        int res[100] = {0};
        res[0] = 1;
        for(int i = 0; i < m; i++)
        {
            for(int j = 1; j < n; j++)
            {
                res[j] += res[j-1];
            }
        }
        return res[n-1];
    }
};

Unique Paths II
 
ここで障害物の場合、値が1であれば、ここに障害物があるという意味で、乗り越えられません.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is  2.
ノート:
 
m
 and 
n
 will be at most 100.

class Solution {
public:
    int uniquePathsWithObstacles(vector > &obstacleGrid) {
        if(obstacleGrid.empty() || obstacleGrid[0].empty())
        {
            return 0;
        }
        int res[100] = {0};//if(j == 0)
                {
                    if(obstacleGrid[i][j] == 1)  //
                else
                {
                    if(obstacleGrid[i][j] == 1)
                    {
                        res[j] = 0;
                    }
                    else
                    {
                        res[j] += res[j-1];
                    }
                }
            }
        }
        return res[n-1];
    }
};