Finding the highest value in a matrix using dynamic programming starting from top left to bottom right.

I am trying to move top left of the matrix to bottom right, with right and down movements counting as -1 and not taking the data in the matrix. Only diagonal movements can be added. From my code, I am getting 24 instead 17 and I am not sure why. path should be down, -1, 19,18, then 17

data=[0 5 1 100; 1 1 5 1; 1 20 1 5]

data = 3×4

0 5 1 100 1 1 5 1 1 20 1 5

dp=zeros(size(data));
for  i = 2:size(data, 1)
    dp(i,1)=-1+ dp(i,1);
end
for j = 2:size(data, 2)
    dp(1,j)=-1+ dp(1,j);
end


options=[];

options =

     []

for i = 2:size(data, 1)
    for j = 2:size(data, 2)
       options=[];
        if i==1 && j==1
         best=data(1,1)
             break
       end
       if j>1
        moveRight = dp(i, j-1)-1;
        options(end+1)=moveRight;
        dp(i, j)=moveRight;
       end
       if i>1
            moveDown = dp(i-1, j)-1;
             options(end+1)=moveDown;
             dp(i, j)=moveDown;
       end
       if i>1 && j>1
            moveDiagonal =  dp(i-1, j-1);+ data(i, j);
            options(end+1)=moveDiagonal;
            dp(i, j) = data(i, j) + max(options);

       end

    end
end

highestValue = dp(end, end)

highestValue = 24

[Matt J]

So, the problem is resolved?

[Anthony Chan]

No, just extra info added

[dpb]

data=[0 5 1 100; 1 1 5 1; 1 20 1 5];
dp=zeros(size(data));
dp(2:end,1)=-1;
dp(1,2:end)=-1;
dp

I don't understand the problem description enough to know what the problem trying to be solved actually is, but "the MATLAB way" in the initialization phase is to use array indexing vector operations as show above.

If the problem is one of decision making on a stepwise basis, then a loop construct is probably required, but learning the basics of array indexing operations early on is a key to productive use of MATLAB.

Answer 1

[Hassaan]

@Anthony Chan Try this:

• Initialize the first row and column of dp to account for the -1 cost of moving right or down.
• Correctly calculate and update the DP values for each cell by considering all possible moves (right, down, diagonal) but prioritizing diagonal moves with the addition of data(i, j) when both moves are available.
• Ensure that the selection of the best move (especially for diagonal moves) correctly reflects the total score of reaching that cell.

data = [0 5 1 100; 1 1 5 1; 1 20 1 5];
dp = zeros(size(data));

% Initialize the first row and column
for i = 2:size(data, 1)
    dp(i, 1) = dp(i-1, 1) - 1;
end
for j = 2:size(data, 2)
    dp(1, j) = dp(1, j-1) - 1;
end

% Fill in the dp matrix
for i = 2:size(data, 1)
    for j = 2:size(data, 2)
        moveRight = dp(i, j-1) - 1;
        moveDown = dp(i-1, j) - 1;
        moveDiagonal = dp(i-1, j-1) + data(i, j);
        % Choose the best option, prioritizing diagonal move
        dp(i, j) = max([moveRight, moveDown, moveDiagonal]);
    end
end

highestValue = dp(end, end);

disp(highestValue)

    17

-----------------------------------------------------------------------------------------------------------------------------------------------------

If you find the solution helpful and it resolves your issue, it would be greatly appreciated if you could accept the answer. Also, leaving an upvote and a comment are also wonderful ways to provide feedback.

It's important to note that the advice and code are based on limited information and meant for educational purposes. Users should verify and adapt the code to their specific needs, ensuring compatibility and adherence to ethical standards.

Professional Interests

• Technical Services and Consulting
• Embedded Systems | Firmware Developement | Simulations
• Electrical and Electronics Engineering

Feel free to contact me.