CareerCup

use DP
traverse from left to right and up to down.
cost[i][j]= min(cost[i-1][j] + possible_cost, cost[i][j-1] + possible_cost)
got it at last.

follow up:
start from right bottom, use the cost value to get the previous point (either [i-1][j] or [i][j-1]) and print it. do it iteratelly to reach the start point.

public int minCost(final int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return -1;
        }

        for (int x = 1; x < matrix[0].length; ++x) {
            matrix[0][x] = Math.max(matrix[0][x], matrix[0][x - 1]);
        }
        for (int y = 1; y < matrix[0].length; ++y) {
            matrix[y][0] = Math.max(matrix[y][0], matrix[y - 1][0]);
        }


        for (int y = 1; y < matrix.length; ++y) {
            for (int x = 1; x < matrix[0].length; ++x) {
                matrix[y][x] = Math.max(matrix[y][x], Math.min(matrix[y][x - 1], matrix[y - 1][x]));
            }
        }
        return matrix[matrix.length - 1][matrix[0].length - 1] - matrix[0][0];
    }


    public List<int[]> shortestPath(final int[][] matrix) {
        int minPath = minCost(matrix);
        if (minPath == -1) {
            return null;
        }

        List<int[]> path = new ArrayList<>(matrix.length + matrix[0].length - 1);
        int x = matrix[0].length - 1;
        int y = matrix.length - 1;

        addPath(path, x, y);
        while (x != 0 || y != 0) {
            if (x > 0 && y > 0) {
                if (matrix[y - 1][x] > matrix[y][x - 1]) {
                    addPath(path, x - 1, y);
                    --x;
                } else {
                    addPath(path, x, y - 1);
                    --y;
                }
            } else if (x > 0) {
                addPath(path, x - 1, y);
                --x;
            } else {
                addPath(path, x, y - 1);
                --y;
            }
        }
        return path;
    }

    private void addPath(final List<int[]> path, final int x, final int y) {
        path.add(new int[]{x, y});
    }

Old good Dijkstra

import java.util.*;

class RobotPaths {

	final int[][] heights;
	final int M;
	final int N;

	RobotPaths(int[][] heights) {
		this.heights = heights;
		N = heights.length - 1;
		M = heights[0].length - 1;
		END = new Node(N, M);
	}

	final Node ORIGIN = new Node(0, 0);
	final Node END;

	class Node {
		final int x;
		final int y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

		int height() {
			return heights[x][y];
		}

		List<Node> neighbours() {
			List<Node> n = new ArrayList<>();
			if (x < N) {
				n.add(new Node(x + 1, y));
			}
			if (y < M) {
				n.add(new Node(x, y + 1));
			}
			if (x > 0) {
				n.add(new Node(x - 1, y));
			}
			if (y > 0) {
				n.add(new Node(x, y - 1));
			}
			return n;
		}

		public boolean equals(Object that) {
			Node p2 = (Node)that;
			return x == p2.x && y == p2.y;
		}

		public int hashCode() {
			return x << 16 + y;
		}

		public String toString() {
			return String.format("[%d, %d]", y, x);
		}
	}

	int cost(Node from, Node to) {
		return Math.max(to.height() - from.height(), 0);
	}

	class Solution {
		List<Node> minPath;
		int minCost;

		Solution(List<Node> minPath, int minCost) {
			this.minPath = minPath;
			this.minCost = minCost;
		}
	}

	Solution findShortest() {
		Map<Node, Integer> costMap = new HashMap<>();
		Map<Node, Node> prevMap = new HashMap<>();
		Comparator<Node> comp = new Comparator<Node>() {
			public int compare(Node n1, Node n2) {
				int i1 = costMap.getOrDefault(n1, Integer.MAX_VALUE);
				int i2 = costMap.getOrDefault(n2, Integer.MAX_VALUE);
				return i1 - i2;
			}
		};
		List<Node> todo = new ArrayList<>();
		todo.add(ORIGIN);
		costMap.put(ORIGIN, 0);
		while (!todo.isEmpty()) {
			Node curr = todo.remove(0);
			Integer currCost = costMap.get(curr);
			for (Node n : curr.neighbours()) {
				if (!costMap.containsKey(n)) {
					todo.add(n);
				}
				Integer prevCost = costMap.getOrDefault(n, Integer.MAX_VALUE);
				int newCost = cost(curr, n) + currCost;
				if (newCost < prevCost) {
					costMap.put(n, newCost);
					prevMap.put(n, curr);
				}
			}
			Collections.sort(todo, comp);
		}
		LinkedList<Node> res = new LinkedList<>();
		Node curr = END;
		while (curr != ORIGIN) {
			res.addFirst(curr);
			curr = prevMap.get(curr);
		}
		res.addFirst(ORIGIN);
		return new Solution(res, costMap.get(END));
	}

	static final int[][] heights1 = {
			{ 0, 1, 2, 3, 4 },
			{ 1, 0, 3, 4, 5 },
			{ 2, 1, 0, 5, 6 },
			{ 3, 4, 1, 0, 7 },
			{ 4, 5, 6, 1, 0 }
	};

	static final int[][] heights2 = {
			{ 0, 1, 0, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, 1, 0 }
	};

	static final int[][] heights3 = {
			{ 0, 1, 0, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
			{ 0, 0, 0, 1, 0, 0, 0, 1, 0 }
	};

	public static void main(String[] args) {
		assertEquals(new RobotPaths(heights1).findShortest().minCost, 4);
		assertEquals(new RobotPaths(heights2).findShortest().minCost, 0);
		assertEquals(new RobotPaths(heights3).findShortest().minCost, 0);
	}

	static void assertEquals(int n1, int n2) {
		if (n1 != n2) {
			throw new AssertionError("found " + n1 + " expected " + n2);
		}
	}
}

Isn't this just min-path in a weighted graph? Use Dijkstra's algorithm.