Can you explain the logic of the code?

#1

Why he is adding sum[i][j] to calculate minCost for dp[i][j] in the lecture??

#2

hi… can u share the code u are referring to??

#3 
#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()
#define clr(x,y) memset(x, y, sizeof(x))
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define deb(x) cout << #x << “=” << x << endl;
#define deb2(x, y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl;
template using pbds = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update> ;
const int N = 100005;
vector prime;
bool ar[N];

//ll dp[N];
//ll arr[N];
// map<ll,ll> dp;
//vector dp(N);
/******************************************************************************************************************************/

void seive()
{
for (ll i = 0; i < N; i++) ar[i] = true;
ar[0] = ar[1] = false;
for (ll i = 2; i < N; i++)
{
if (ar[i] == true)
{
prime.push_back(i);
for (ll j = i * i ; j < N; j += i)
{
ar[j] = false;
}
}
}

}

ll power(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
ans *= a;
//ans %= c;
a *= a;
//a %= c;
b /= 2;
}
return ans;//%c;
}

ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}

ll dp[405][405];

ll solve(int i, int j, int n, vector &v, vector &cum_sum)
{
if (i == j) return 0;
if (dp[i][j] != -1) return dp[i][j];

ll ans = inf;
for (int k = i; k < j; k++)
{
	ll cur = cum_sum[j] - cum_sum[i - 1] + solve(i, k, n, v, cum_sum) + solve(k + 1, j, n, v, cum_sum);
	ans = min(ans, cur);
}

return dp[i][j] = ans;

}

int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

ll t = 1, n, i, j, m, k, l, ans = 0, x = 0, y = 0, sum = 0, c, d, a = 0, b = 0;

cin >> n;
vector<ll> v(n + 1), cum_sum(n + 1, 0);
for (i = 1; i <= n; i++)
{
	cin >> v[i];
	cum_sum[i] = cum_sum[i - 1] + v[i];
}

memset(dp, -1, sizeof dp);

ans = solve(1, n, n, v, cum_sum);

cout << ans << endl;

}

#4

see the solve() function… Here just one change I made is that instead of writing sum[i][j], I have written cum_sum[j]-cum_sum[i-1] i.e sum of all elements from index i to j. So why it is adding the sum of all elements for i to j for calculating cur…

#5

cum_sum[j]-cum_sum[i-1]
will give u the sum of all elements from i to j only… whats doubt over here??

#6

I know it gives sum of all elements from i to j, but why he is adding this sum here?? what is the logic behind this??

#7

it is basically sum of all elements from i to j bcoz he has maintained a cumulative sum array… so in order to get sum of elements from i to j he has to subtract sum of i-1 elements…

#8

you didn’t get my question… I am not asking how to calculate the sum of all elements from i to j, I know well how to calculate this sum from i to j using a cumulative sum array…

I am asking to explain the logic of calculating dp[i][j] state… in order to calculate dp[i][j] why he is adding the sum of elements from I to j.
I mean just explain this line of code…
ll cur = cum_sum[j] - cum_sum[i - 1] + solve(i, k, n, v, cum_sum) + solve(k + 1, j, n, v, cum_sum);
here why he wrote cum_sum[j] - cum_sum[i - 1]

#9

this cost is the cost of combining the leftans and the rightans

#10

i hope it clears all ur doubts??

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.