【每日算法】动态规划六

2022-10-25Java58

难度[中等]

&#x7ED9;&#x4F60;&#x4E00;&#x4E2A;&#x6B63;&#x6574;&#x6570;&#x6570;&#x7EC4; values&#xFF0C;&#x5176;&#x4E2D; values[i]&#xA0;&#x8868;&#x793A;&#x7B2C; i &#x4E2A;&#x89C2;&#x5149;&#x666F;&#x70B9;&#x7684;&#x8BC4;&#x5206;&#xFF0C;&#x5E76;&#x4E14;&#x4E24;&#x4E2A;&#x666F;&#x70B9;&#xA0;i &#x548C;&#xA0;j&#xA0;&#x4E4B;&#x95F4;&#x7684; &#x8DDD;&#x79BB; &#x4E3A;&#xA0;j - i&#x3002;

&#x4E00;&#x5BF9;&#x666F;&#x70B9;&#xFF08;i < j&#xFF09;&#x7EC4;&#x6210;&#x7684;&#x89C2;&#x5149;&#x7EC4;&#x5408;&#x7684;&#x5F97;&#x5206;&#x4E3A; values[i] + values[j] + i - j &#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x666F;&#x70B9;&#x7684;&#x8BC4;&#x5206;&#x4E4B;&#x548C; &#x51CF;&#x53BB; &#x5B83;&#x4EEC;&#x4E24;&#x8005;&#x4E4B;&#x95F4;&#x7684;&#x8DDD;&#x79BB;&#x3002;

&#x8FD4;&#x56DE;&#x4E00;&#x5BF9;&#x89C2;&#x5149;&#x666F;&#x70B9;&#x80FD;&#x53D6;&#x5F97;&#x7684;&#x6700;&#x9AD8;&#x5206;&#x3002;

&#x793A;&#x4F8B; 1&#xFF1A;

&#x8F93;&#x5165;&#xFF1A;values = [8,1,5,2,6]
&#x8F93;&#x51FA;&#xFF1A;11
&#x89E3;&#x91CA;&#xFF1A;i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
&#x793A;&#x4F8B; 2&#xFF1A;

&#x8F93;&#x5165;&#xFF1A;values = [1,2]
&#x8F93;&#x51FA;&#xFF1A;2