# Rod-Cutting Problem (Rod-Cutting Problem)

Jump to navigation
Jump to search

## Description

Given a rod of length $n$, and prices $p_i$ for which one can sell a segment of the rod of length $i$ ($1 \leq i \leq n$), find the splitting of the rod for which one can earn the most money once they sell the rod segments produced.

## Parameters

$n$: length of rod

## Table of Algorithms

Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|

Brute Force | 1940 | $O(n*{2}^n)$ | $O(n)$ | Exact | Deterministic | |

Dynamic Programming | 1953 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic |