長さ n インチの棒が与えられます。整数の長さのさまざまな部分に切り取ることができます。あなたの目標は、可能なすべての部分の長さの積を最大にすることです。少なくとも 1 つのカットを作成する必要があります。ロープの長さは 2 メートル以上と仮定します。参考：https ://www.geeksforgeeks.org/maximum-product-cutting-dp-36/
その他の参考文献:ロッドをカットして利益を最大化するためのアルゴリズム
2Dテーブルを使用したボトムアップの動的計画法を使用して、この質問を行いたいです。
長さが 5 であるとします。
Length of rod
[1] [2] [3] [4] [5]
[0] 0 0 0 0 0
Number of [1] 0 1 2 4 6
cuts [2] 0 1 2
[3] 0
各セルは、特定の長さのロッドで指定されたカット数で得られる最大製品と、カット後に残った最大長を示します。
たとえば、セルにカット数 2 とロッドの長さ 4 を入力する必要があるとします。各セルには、特定の長さの最大製品を格納するだけでなく、カット後に残った最大の長さも格納すると仮定します。
長さ 4 を 1 回カットした後、左部分を 2 に、右部分を 2 にカットするため、最大積は 4 になります。最大積の 4 と最大部分の 2 の 2 つの数値を保存します。セル (2, 4) にいるときは、カットできるかできないかのどちらかです。カットを行わない場合は、現在の行を調べます。そして、それぞれの長さをループします。この場合、長さ 2 と長さ 3 をループします。長さが 2 の場合は、残りの 4-2=2 があり、乗算して 4 を取得します。次に、残りの長さを取得するために 3 で同じことを行います。を 1 にして、これに 2 を掛けると 2 になります。
もう 1 つのオプションは、カットを行うことです。次に、上の行を確認する必要があります。また、その行の先頭からループします。次に、最大値を選択します。
私の問題は、すべての列をループするたびに、つまり左から現在のセルまでループする必要があることです。これにより、時間の複雑さが O(n^3) になります。
2D テーブルを使用する代わりに O(n^2) でこれを行う方法はありますか?