Explain the dp approach

Please explain the dynaminc programming applied in the solution. Also provide its editorial for better understanding.

Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Some greedy algorithms (such as Kruskal’s or Prim’s for minimum spanning trees) are however proven to lead to the optimal solution.

For example, in the coin change problem of finding the minimum number of coins of given denominations needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount. In contrast, a greedy algorithm might treat the solution as a sequence of coins, starting from the given amount and at each step subtracting the largest possible coin denomination that is less than the current remaining amount. If the coin denominations are 1,4,5,15,20 and the given amount is 23, this greedy algorithm gives a non-optimal solution of 20+1+1+1, while the optimal solution is 15+4+4.

I said the dp applied in given solution.

@gautamcse27 In this question dp[i][j] stores the number of programs possible till instruction i and indentation j. So if the last letter was f that means next statement has to be indented, say x programs were possible before i+1 instruction and ith instruction was ‘f’.

Now also x programs are possible because new statement will just be added with a indentation that’s why first loop just assign values dp[i][j] to dp[i-1][j-1] that is all the programs ending at instruction i with an extra indentation (due to for loop ) are same as programs ending at i-1 instruction at indentation j-1 (1 less than ith one).
Now if it last statement is ‘s’ then new statement can take any one of values till indentation i. You see since all are different cases we just add them all and for that we have to keep prefix array because for every indentation we are finding maximum possible programs.

Hence we add dp[i][j+1] (this would be 0 for j=n) and dp[i-1][j] and assign it to dp[i][j].
Hope this cleared your query :slight_smile:

how to count indent?

indent can be at max i for i+1 instruction (for case ‘s’ as the last instruction because if last is ‘s’ you can have atmost indentation to that of last instruction). So that’s why we have taken sum of all which means that all possible programs till indent i …i.e. 0<j<i we have to add and this is for ‘s’.
Here second dimension of array stores the number by which instruction is indented so we are not calculating indentation but number of valid programs.