حل تشریحی سوال شماره 37 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

می خواهیم یک قطعه چوب به طول L را از نقاط $x_1$ تا $x_{n-1}$ که فاصله برش‌ k ام از انتهای چپ قطعه چوب است ببریم فرض کنید $x_0=0$ و $x_n=L$) میدانیم که هزینه برش یک قطعه چوب به اندازه m متر از هر نقطه برابر m تومان است (مستقل از مکان نقطه برش) زیر مسئله $P_{i,j}$ که $i<j$ را قطعه چوب بین نقاط $x_i$ و $x_j$ در نظر میگیریم که باید از نقاط $x_{i+1}$ تا $x_{j-1}$ بریده شود. مسئله اصلی $P_{0,n}$ است. اگر r اولین نقطه برش برای $P_{i,j}$ و $C_{i,j}$ همچنین $C_{i,j}$ هزینه کمینه این زیر مسئله باشد آنگاه $C_{i,j}$ برابر کدام یک از رابطه های زیر است؟

$\left(C_{i,i}=C_{i,i+1}=0\right)$