JAVA动态规划,最长递增子序列的代码太难理解,求大神帮我讲解一下!

Python014

JAVA动态规划,最长递增子序列的代码太难理解,求大神帮我讲解一下!,第1张

第一层的 if 逻辑表示 如果新的一个数A[i]对于 B[]中的数来说是递增的,则len加1,这是记录递增数列长度的主要逻辑。else中的逻辑保证B[]中的数列是最新的递增数列。

举个例子,如果A数组为[1,2,3,4,5, 3.1, 3.2, 3.3, 3.4]

当i=4时 len=4 B=[x,1,2,3,4,x] 循环结束后 len=5 B=[x,1,2,3,4,5] 第一层判断走if

当i=5时 len=5 B=[x,1,2,3,4,5] 循环结束后 len=5 B=[x,1,2,3,3.1,5] 第一层判断走else

当i=6时 len=5 B=[x,1,2,3,3.1,5] 循环结束后 len=5 B=[x,1,2,3,3.1,3.2] 第一层判断走else

当i=7时 len=5 B=[x,1,2,3,3.1,3.2] 循环结束后 len=6 B=[x,1,2,3,3.1,3.2,3.3] 第一层判断走else

...

其中第一层的else中做的工作就是把B从[x,1,2,3,4,5] 一步步变成 [x,1,2,3,3.1,3.2],最终B[]的最后一个元素变成3.2, 在下一次A[i]=3.3的时候,就又会走第一次if的逻辑(len加1)了。

public class MyClass {

    public static void main(String[] args) {

        System.out.println(">>> result count:" + method(6, 3))

    }

    public static int method(int n, int k) {

        List<List<Integer>> list = new ArrayList<>()

        for (int i = 0 i < k i++) {

            if (i == 0) {

                for (int j = 1 j < n j++) {

                    List<Integer> li = new ArrayList<>()

                    li.add(j)

                    list.add(li)

                }

                continue

            }

            List<List<Integer>> listNew = new ArrayList<>()

            for (List<Integer> integers : list) {

                for (int j = integers.get(integers.size() - 1) j < n j++) {

                    List<Integer> li = new ArrayList<>()

                    li.addAll(integers)

                    li.add(j)

                    listNew.add(li)

                    if (i + 1 == k) {

                        int res = 0

                        for (Integer integer : li) {

                            res += integer

                        }

                        if (res != n) {

                            listNew.remove(li)

                        }

                    }

                }

            }

            list.clear()

            list.addAll(listNew)

        }

        for (List<Integer> integers : list) {

            for (Integer integer : integers) {

                System.out.print(integer + "\t")

            }

            System.out.println()

        }

        return list.size()

    }

}