java - n x n 整数矩阵求最大和的动态规划算法

Question

我对下面的问题理解起来比较困难，如果有人能帮助我理解它，我将不胜感激。问题是:

Implement a dynamic programming algorithm for solving the following
problem. The input is an n × n matrix of integers. For the output: 
compute the largest sum of adjacent entries in horizontal, vertical,
diagonal and anti-diagonal direction. Return as output the sum 
h + v + d + c (in suggestive notation) of those four auxiliary results.
The largest (or maximal) sum of an array consisting of only negative  
integers is 0; that is, in that case we select the empty subarray.
A (small) example input matrix with solution 45:
|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

我的意思是如果有人能帮助我朝着正确的方向前进，我将非常感激!!!谢谢

Answer 1

鉴于您的问题陈述:

Implement a dynamic programming algorithm for solving the following problem. The input is an n × n matrix of integers. For the output: compute the largest sum of adjacent entries in horizontal, vertical, diagonal and anti-diagonal direction. Return as output the sum h + v + d + c (in suggestive notation) of those four auxiliary results. The largest (or maximal) sum of an array consisting of only negative
integers is 0; that is, in that case we select the empty subarray. A (small) example input matrix with solution 45:

|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

然后，阅读您发布的示例输入，我做了一个从文件中解析该信息的简短方法:

public static List<List<Integer>> readFile(final String path) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Path p = Paths.get(path);
    if (!Files.exists(p))
        return null;
    List<String> lines = null;
    try {
        lines = Files.readAllLines(p);
    } catch (IOException e) {
        e.printStackTrace();
    }
    if (lines == null)
        return null;
    for (String str : lines) {
        List<Integer> row = new ArrayList<Integer>();
        final String line = str.substring(1, str.length() - 1);
        String[] arr = line.split(" ");
        for (String s : arr)
            row.add(Integer.valueOf(s.trim()));
        result.add(row);
    }
    return result;
}

垂直方法很简单，遍历嵌套数组。

    public static int getVertical(final List<List<Integer>> list) {
        int result = 0;
        for (List<Integer> arr : list) {
            int curr = 0;
            for (Integer val : arr)
                curr += val;
            if (curr > result)
                result = curr;
        }
        return result;
    }

水平方向也很直接。注意:为了简单起见，我在这里只使用了一个计数器列表。有更有效的方法。

    public static int getHorizontal(final List<List<Integer>> list, final int len) {
        List<Integer> sums = new ArrayList<Integer>(list.get(0));
        for (int i = 1; i < len; ++i)
            for (int j = 0; j < len; ++j)
                sums.set(j, sums.get(j) + list.get(i).get(j));
        return Collections.max(sums);
    }

我快速搜索找到诊断/反诊断循环 question .此代码有助于适应整数值(来自字符串/println 的)并产生以下两种方法。注意:debug/system.out.println 用于帮助/显示。

    public static int getDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int i = len - 1; i > 0; --i) {
            //String temp = "";
            int tmp = 0;
            for (int j = 0, x = i; x <= len - 1; ++j, ++x) {
                final int val = list.get(x).get(j);
                //temp = temp + " " + val;
                tmp += val;
            }
            //System.out.println(temp);
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int i = 0; i <= len - 1; ++i) {
            //String temp = "";
            int tmp = 0;
            for (int j = 0, y = i; y <= len - 1; ++j, ++y) {
                final int val = list.get(j).get(y);
                //temp = temp + " " + val;
                tmp += val;
            }
            //System.out.println(temp);
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static int getAntiDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int k = 0; k < len; ++k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(i).get(j);
                //System.out.print(val + " ");
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
            //System.out.println();
        }
        // [lower half]
        for (int k = len - 2; k >= 0; --k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(len - j - 1).get(len - i - 1);
                //System.out.print(val + " ");
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
            //System.out.println();
        }
        return result;
    }

这是解决原始问题的整个程序的最终结果:

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class App {
    public static void main(String[] args) {
        List<List<Integer>> data = readFile("C:\\Users\\Nick\\Desktop\\test.txt");
        for (List<Integer> row : data)
            System.out.println(row);
        final int n = data.size();
        int maxVertical = getVertical(data);
        int maxHorizontal = getHorizontal(data, n);
        int maxDiagonal = getDiagonal(data, n);
        int maxAntiDiagonal = getAntiDiagonal(data, n);
        System.out.println("max vertical = " + maxVertical);
        System.out.println("max horizontal = " + maxHorizontal);
        System.out.println("max diagonal = " + maxDiagonal);
        System.out.println("max anti-diagonal = " + maxAntiDiagonal);
    }
    public static int getVertical(final List<List<Integer>> list) {
        int result = 0;
        for (List<Integer> arr : list) {
            int curr = 0;
            for (Integer val : arr)
                curr += val;
            if (curr > result)
                result = curr;
        }
        return result;
    }
    public static int getHorizontal(final List<List<Integer>> list, final int len) {
        List<Integer> sums = new ArrayList<Integer>(list.get(0));
        for (int i = 1; i < len; ++i)
            for (int j = 0; j < len; ++j)
                sums.set(j, sums.get(j) + list.get(i).get(j));
        return Collections.max(sums);
    }
    public static int getDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int i = len - 1; i > 0; --i) {
            int tmp = 0;
            for (int j = 0, x = i; x <= len - 1; ++j, ++x) {
                final int val = list.get(x).get(j);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int i = 0; i <= len - 1; ++i) {
            int tmp = 0;
            for (int j = 0, y = i; y <= len - 1; ++j, ++y) {
                final int val = list.get(j).get(y);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static int getAntiDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int k = 0; k < len; ++k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(i).get(j);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int k = len - 2; k >= 0; --k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(len - j - 1).get(len - i - 1);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static List<List<Integer>> readFile(final String path) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Path p = Paths.get(path);
        if (!Files.exists(p))
            return null;
        List<String> lines = null;
        try {
            lines = Files.readAllLines(p);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (lines == null)
            return null;
        for (String str : lines) {
            List<Integer> row = new ArrayList<Integer>();
            final String line = str.substring(1, str.length() - 1);
            String[] arr = line.split(" ");
            for (String s : arr)
                row.add(Integer.valueOf(s.trim()));
            result.add(row);
        }
        return result;
    }
}

最后，假设 test.txt 文件包含:

|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

输出结果(应该是)是:

[-2, 5, 3, 2]
[9, -6, 5, 3]
[1, -8, 2, -3]
[-1, 2, -5, 2]
max vertical = 11
max horizontal = 7
max diagonal = 7
max anti-diagonal = 14

干杯

编辑我意识到我在技术上没有完全回答原始问题，所以:

1. 将这两行添加到 main() 方法的最后

   int result = maxVertical + maxHorizo​​ntal + maxDiagonal + maxAntiDiagonal;System.out.println("结果 = "+ 结果);

2. 为每个相应的方法(vert/horiz/diag/anti-diag)添加检查，以便在问题中陈述负面事件的情况

The largest (or maximal) sum of an array consisting of only negative integers is 0; that is, in that case we select the empty subarray

也可以被覆盖。这不是一个巨大的代码检修，而是一个独特的检查。