剑指offer-剪绳子

剪绳子

给一根一段长度为n的绳子，请把绳子剪成m段，每一段绳子为k[0] k[1] … k[m]，请问k[0]*k[1]…k[m]可能的乘积是多少？例如长度为8的绳子，我们把它剪成长度为2 3 3的三段，此时得到的最大乘积是18。

思路

把长度为n的绳子剪成若干段后各段长度乘积，剪第一刀的时候，有n-1中可能的选择，也就是长度分别为1,2,…n-1，因此f(n) = max(f(i)*f(n-i))，其中0<i<n。

这样的话就是从上到下的递归公式，会产生很多重复的子问题，从而产生大量不必要的重复计算。更好的方式是通过从下到上的顺序计算，也就是可以先得到f(2)、f(3)，再得到f(4)、f(5)，直到得到f(n)

代码

function maxProductAfterCutting_solution(length) {
    if (length === 1) {
        return 0;
    }
    if (length === 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }

    const products = new Array(length + 1);
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;

    let max = 0;

    for (let i=4; i <= length; i++) {
        max = 0;
        for (let j=1; j <= i/2; j++) {
            let product = products[j] * products[i - j];
            if (max < product) {
                max = product;
            }
            products[i] = max;
        }
    }

    max = products[length];
    return max;
}

复杂度分析

时间复杂度: O(N*M)
空间复杂度: O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

剪绳子

思路

代码

复杂度分析

CATALOG

FEATURED TAGS

FRIENDS