"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", blockquote: "blockquote", code: "code", h2: "h2", h3: "h3", h4: "h4", hr: "hr", img: "img", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msub: "msub", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsxs(_components.h2, { id: "动态规划", children: [_jsx(_components.a, { className: "heading-link", href: "#动态规划", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "动态规划"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["\n", _jsx(_components.p, { children: "动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。" }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsx(_components.p, { children: "动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。" }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsx(_components.p, { children: "使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。" }), "\n"] }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//algorithm" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "class" }), " ", _jsx(_components.span, { className: "token class-name", children: "Solution" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "public" }), _jsx(_components.span, { className: "token operator", children: ":" }), "\n"] })] }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "笔记", children: [_jsx(_components.a, { className: "heading-link", href: "#笔记", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "笔记"] }), "\n", _jsxs(_components.h4, { id: "动态规划代码框架", children: [_jsx(_components.a, { className: "heading-link", href: "#动态规划代码框架", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "动态规划代码框架"] }), "\n", _jsx(_components.pre, { className: "language-py", children: _jsxs(_components.code, { className: "language-py code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "# 初始化 base case" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["dp", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " base\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "# 状态转移" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "for" }), " 状态", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token keyword", children: "in" }), " 状态", _jsx(_components.span, { className: "token number", children: "1" }), "的所有取值", _jsx(_components.span, { className: "token punctuation", children: ":" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " 状态", _jsx(_components.span, { className: "token number", children: "2" }), " ", _jsx(_components.span, { className: "token keyword", children: "in" }), " 状态", _jsx(_components.span, { className: "token number", children: "2" }), "的所有取值", _jsx(_components.span, { className: "token punctuation", children: ":" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" dp", _jsx(_components.span, { className: "token punctuation", children: "[" }), "状态", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), "状态", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " 求最值", _jsx(_components.span, { className: "token punctuation", children: "(" }), "选择", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " 选择", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] })] }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "509-斐波那契数", children: [_jsx(_components.a, { className: "heading-link", href: "#509-斐波那契数", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "509. 斐波那契数"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。" }), "\n"] }), "\n", _jsx(_components.p, { children: "类似题目如" }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["tribonacci ：", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] })] }), _jsx(_components.mo, { children: "=" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "3" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] })] }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "2" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] })] }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "−" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T_{(n)}=T_{(n-3)}+T_{(n-2)}+T_{(n-1)}" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0385em", verticalAlign: "-0.3552em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3448em" }, children: _jsxs(_components.span, { style: { top: "-2.5198em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mopen mtight", children: "(" }), _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mclose mtight", children: ")" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.3552em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0385em", verticalAlign: "-0.3552em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3448em" }, children: _jsxs(_components.span, { style: { top: "-2.5198em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mopen mtight", children: "(" }), _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "3" }), _jsx(_components.span, { className: "mclose mtight", children: ")" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.3552em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0385em", verticalAlign: "-0.3552em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3448em" }, children: _jsxs(_components.span, { style: { top: "-2.5198em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mopen mtight", children: "(" }), _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "2" }), _jsx(_components.span, { className: "mclose mtight", children: ")" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.3552em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0385em", verticalAlign: "-0.3552em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.13889em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3448em" }, children: _jsxs(_components.span, { style: { top: "-2.5198em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mopen mtight", children: "(" }), _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }), _jsx(_components.span, { className: "mbin mtight", children: "−" }), _jsx(_components.span, { className: "mord mtight", children: "1" }), _jsx(_components.span, { className: "mclose mtight", children: ")" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.3552em" }, children: _jsx(_components.span, {}) }) })] }) })] })] })] })] })] }), "\n", _jsx(_components.li, { children: "爬梯子" }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "方法一：迭代" }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//algorithm" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "class" }), " ", _jsx(_components.span, { className: "token class-name", children: "Solution" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "public" }), _jsx(_components.span, { className: "token operator", children: ":" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "fib" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "==" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "==" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: ">=" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " n_2 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " n_1 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " n_", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<=" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token operator", children: "++" }), "i", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" n_ ", _jsx(_components.span, { className: "token operator", children: "=" }), " n_2 ", _jsx(_components.span, { className: "token operator", children: "+" }), " n_1", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" n_2 ", _jsx(_components.span, { className: "token operator", children: "=" }), " n_1", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" n_1 ", _jsx(_components.span, { className: "token operator", children: "=" }), " n_", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " n_", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsx(_components.p, { children: "方法二：带记忆的递归" }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//algorithm" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "class" }), " ", _jsx(_components.span, { className: "token class-name", children: "Solution" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "public" }), _jsx(_components.span, { className: "token operator", children: ":" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "static" }), " vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " v", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "Solution" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" v", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" v", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "fib" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: ">=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "fib" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token function", children: "fib" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " Solution", _jsx(_components.span, { className: "token double-colon punctuation", children: "::" }), "v ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsxs(_components.span, { className: "token generic-function", children: [_jsx(_components.span, { className: "token function", children: "vector" }), _jsxs(_components.span, { className: "token generic class-name", children: [_jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" })] })] }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token number", children: "100" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//entry" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " n ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "input", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cout ", _jsx(_components.span, { className: "token operator", children: "<<" }), " so", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "fib" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//test" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token number", children: "1" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token number", children: "22" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token number", children: "30" }), "\n"] })] }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "746-使用最小花费爬楼梯", children: [_jsx(_components.a, { className: "heading-link", href: "#746-使用最小花费爬楼梯", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "746. 使用最小花费爬楼梯"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。" }), "\n", _jsx(_components.p, { children: "每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。" }), "\n", _jsx(_components.p, { children: "请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " v", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " record", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "minCostClimbingStairs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " cost", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" v ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsxs(_components.span, { className: "token generic-function", children: [_jsx(_components.span, { className: "token function", children: "vector" }), _jsxs(_components.span, { className: "token generic class-name", children: [_jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" })] })] }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cost", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" record ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsxs(_components.span, { className: "token generic-function", children: [_jsx(_components.span, { className: "token function", children: "vector" }), _jsxs(_components.span, { className: "token generic class-name", children: [_jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" })] })] }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cost", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cost", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "costv" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), " ", _jsx(_components.span, { className: "token operator", children: "&&" }), " n ", _jsx(_components.span, { className: "token operator", children: ">=" }), " v", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " v", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: ">=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " path1 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token function", children: "costv" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " path2 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token function", children: "costv" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "path1 ", _jsx(_components.span, { className: "token operator", children: "<" }), " path2 ", _jsx(_components.span, { className: "token operator", children: "?" }), " path1 ", _jsx(_components.span, { className: "token operator", children: ":" }), " path2", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//entry" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " cost", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "input", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cost", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "push_back" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["cout ", _jsx(_components.span, { className: "token operator", children: "<<" }), " so", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "minCostClimbingStairs" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cost", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//test" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsx(_components.code, { className: "language-cpp code-highlight", children: _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "100" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "100" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token number", children: "100" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), "\n"] }) }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "198-打家劫舍", children: [_jsx(_components.a, { className: "heading-link", href: "#198-打家劫舍", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "198. 打家劫舍"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。" }), "\n", _jsx(_components.p, { children: "给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " record", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "rob" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" record ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsxs(_components.span, { className: "token generic-function", children: [_jsx(_components.span, { className: "token function", children: "vector" }), _jsxs(_components.span, { className: "token generic class-name", children: [_jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" })] })] }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: ">=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " path1", _jsx(_components.span, { className: "token punctuation", children: "," }), " path2", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" path1 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" path2 ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "recurve" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " n ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " record", _jsx(_components.span, { className: "token punctuation", children: "[" }), "n", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " path1 ", _jsx(_components.span, { className: "token operator", children: ">" }), " path2 ", _jsx(_components.span, { className: "token operator", children: "?" }), " path1 ", _jsx(_components.span, { className: "token operator", children: ":" }), " path2", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//entry" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " cost", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "input", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cost", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "push_back" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "n", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " n", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["cout ", _jsx(_components.span, { className: "token operator", children: "<<" }), " so", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "rob" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cost", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//test" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsx(_components.code, { className: "language-cpp code-highlight", children: _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token number", children: "2" }), " ", _jsx(_components.span, { className: "token number", children: "7" }), " ", _jsx(_components.span, { className: "token number", children: "9" }), " ", _jsx(_components.span, { className: "token number", children: "3" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), "\n"] }) }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "45-跳跃游戏-ii", children: [_jsx(_components.a, { className: "heading-link", href: "#45-跳跃游戏-ii", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "45. 跳跃游戏 II"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "给定一个非负整数数组，你最初位于数组的第一个位置。" }), "\n", _jsx(_components.p, { children: "数组中的每个元素代表你在该位置可以跳跃的最大长度。" }), "\n", _jsx(_components.p, { children: "你的目标是使用最少的跳跃次数到达数组的最后一个位置。" }), "\n", _jsx(_components.p, { children: "假设你总是可以到达数组的最后一个位置。" }), "\n"] }), "\n", _jsxs(_components.p, { children: ["我的思路\r\n(此题可以用贪心法)\r\n", _jsx(_components.img, { src: "https://i.loli.net/2021/07/12/wyHf6YNDM8t7nUu.png", alt: "", className: "internal" })] }), "\n", _jsx(_components.hr, {}), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "jump" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " maxd ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " times ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " \r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// i表示当前所在下标" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "i ", _jsx(_components.span, { className: "token operator", children: "<" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " j ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: "<=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token operator", children: "++" }), "j", _jsx(_components.span, { className: "token punctuation", children: ")" }), " \r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// j表示在i能跳的距离，i+j就是在i能跳到的点" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 看看当前能不能跳到终点" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "i ", _jsx(_components.span, { className: "token operator", children: "+" }), " j ", _jsx(_components.span, { className: "token operator", children: ">=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" maxd ", _jsx(_components.span, { className: "token operator", children: "=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "break" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// maxd 记录当前能跳的点中，能继续跳到的最远距离" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i ", _jsx(_components.span, { className: "token operator", children: "+" }), " j", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " i ", _jsx(_components.span, { className: "token operator", children: "+" }), " j ", _jsx(_components.span, { className: "token operator", children: ">" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "maxd", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "+" }), " maxd", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" maxd ", _jsx(_components.span, { className: "token operator", children: "=" }), " i ", _jsx(_components.span, { className: "token operator", children: "+" }), " j", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token operator", children: "++" }), "times", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" i ", _jsx(_components.span, { className: "token operator", children: "=" }), " maxd", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " times", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//entry" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " v", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " v", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cout ", _jsx(_components.span, { className: "token operator", children: "<<" }), " so", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "jump" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "v", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//test" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsx(_components.code, { className: "language-cpp code-highlight", children: _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "3" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "4" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), "\n"] }) }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "53-最大子序和", children: [_jsx(_components.a, { className: "heading-link", href: "#53-最大子序和", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "53. 最大子序和"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。" }), "\n"] }), "\n", _jsx(_components.p, { children: "示例 1：" }), "\n", _jsx(_components.pre, { children: _jsxs(_components.code, { className: "language-auto code-highlight", children: [_jsx(_components.span, { className: "code-line", children: "输入：nums = [-2,1,-3,4,-1,2,1,-5,4]\r\n" }), _jsx(_components.span, { className: "code-line", children: "输出：6\r\n" }), _jsx(_components.span, { className: "code-line", children: "解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。\n" })] }) }), "\n", _jsx(_components.p, { children: "我使用的分治法" }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "maxSubArray" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token function", children: "divide" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " nums", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "size" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "divide" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " left", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "left ", _jsx(_components.span, { className: "token operator", children: "==" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "left", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " mid ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "left ", _jsx(_components.span, { className: "token operator", children: "+" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "/" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " leftsum ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "divide" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " left", _jsx(_components.span, { className: "token punctuation", children: "," }), " mid", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " rightsum ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "divide" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " mid ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " midsum ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "midSum" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " left", _jsx(_components.span, { className: "token punctuation", children: "," }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "leftsum", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "rightsum", _jsx(_components.span, { className: "token punctuation", children: "," }), " midsum", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsx(_components.span, { className: "code-line", children: "\r\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "midSum" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " left", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " l ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "left ", _jsx(_components.span, { className: "token operator", children: "+" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token operator", children: "/" }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " r", _jsx(_components.span, { className: "token punctuation", children: "," }), " lmax", _jsx(_components.span, { className: "token punctuation", children: "," }), " rmax", _jsx(_components.span, { className: "token punctuation", children: "," }), " cur", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" r ", _jsx(_components.span, { className: "token operator", children: "=" }), " l ", _jsx(_components.span, { className: "token operator", children: "+" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" lmax ", _jsx(_components.span, { className: "token operator", children: "=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "l", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rmax ", _jsx(_components.span, { className: "token operator", children: "=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "r", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cur ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "l ", _jsx(_components.span, { className: "token operator", children: ">=" }), " left", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cur ", _jsx(_components.span, { className: "token operator", children: "+=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "l", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cur ", _jsx(_components.span, { className: "token operator", children: ">=" }), " lmax", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" lmax ", _jsx(_components.span, { className: "token operator", children: "=" }), " cur", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token operator", children: "--" }), "l", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cur ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "r ", _jsx(_components.span, { className: "token operator", children: "<=" }), " right", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cur ", _jsx(_components.span, { className: "token operator", children: "+=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), "r", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "cur ", _jsx(_components.span, { className: "token operator", children: ">=" }), " rmax", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" rmax ", _jsx(_components.span, { className: "token operator", children: "=" }), " cur", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token operator", children: "++" }), "r", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "lmax", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "rmax", _jsx(_components.span, { className: "token punctuation", children: "," }), " lmax ", _jsx(_components.span, { className: "token operator", children: "+" }), " rmax", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.p, { children: "答案的动态规划" }), "\n", _jsx(_components.p, { children: "判断第i个是加入前面，还是独立" }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "maxSubArray" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), _jsx(_components.span, { className: "token operator", children: "&" }), " nums", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " pre ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " maxAns ", _jsx(_components.span, { className: "token operator", children: "=" }), " nums", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "const" }), " ", _jsx(_components.span, { className: "token keyword", children: "auto" }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "x", _jsx(_components.span, { className: "token operator", children: ":" }), " nums", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" pre ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "pre ", _jsx(_components.span, { className: "token operator", children: "+" }), " x", _jsx(_components.span, { className: "token punctuation", children: "," }), " x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" maxAns ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token function", children: "max" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "maxAns", _jsx(_components.span, { className: "token punctuation", children: "," }), " pre", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " maxAns", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsxs(_components.code, { className: "language-cpp code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["Solution so", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//entry" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: ["vector", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token keyword", children: "int" }), _jsx(_components.span, { className: "token operator", children: ">" }), " v", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "if" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "input ", _jsx(_components.span, { className: "token operator", children: ">>" }), " v", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [" cout ", _jsx(_components.span, { className: "token operator", children: "<<" }), " so", _jsx(_components.span, { className: "token punctuation", children: "." }), _jsx(_components.span, { className: "token function", children: "maxSubArray" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "v", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\r\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "//test" }), "\n"] })] }) }), "\n", _jsx(_components.pre, { className: "language-cpp", children: _jsx(_components.code, { className: "language-cpp code-highlight", children: _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "4" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), "\n"] }) }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };