Dynamic Programming

here we can see some of the Dynamic Programming concepts and the sample program to implement those concepts

Normally Dynamic Programming works on the concepts of recursion and

DIVIDE & CONQUER

rule

1) java program to find the maximum number of paths to reach from top left to bottom right of a matrix

import java.util.*;

class Hello {

    static int numberOfPaths(int m, int n)

        if (m == 1 || n == 1)

            return 1;

        return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);

    public static void main(String args[])

        Scanner sc=new Scanner(System.in);

        int R=sc.nextInt();

        int C=sc.nextInt();

        System.out.println(numberOfPaths(R, C));

Sample input:

2 2

Sample output:

There are two paths

(0, 0) -> (0, 1) -> (1, 1)

(0, 0) -> (1, 0) -> (1, 1)

Sample input:

2 3

Sample Output :

There are three paths

(0, 0) -> (0, 1) -> (0, 2) -> (1, 2)

(0, 0) -> (0, 1) -> (1, 1) -> (1, 2)

(0, 0) -> (1, 0) -> (1, 1) -> (1, 2)

Java program to find the maximum cost to reach the end point

import java.util.*;

public class Hello {

    static int min(int x, int y, int z)

        if (x < y)

            return (x < z) ? x : z;

        else

            return (y < z) ? y : z;

    static int minCost(int cost[][], int m, int n)

        if (n < 0 || m < 0)

            return Integer.MAX_VALUE;

        else if (m == 0 && n == 0)

            return cost[m][n];

        else

            return cost[m][n] +

                min( minCost(cost, m-1, n-1),

                     minCost(cost, m-1, n),

                     minCost(cost, m, n-1) );

    public static void main(String args[])

        Scanner sc=new Scanner(System.in);

        int R=sc.nextInt();

        int C=sc.nextInt();

        int[][] cost=new int[R][C];

        for(int i=0;i<R;i++)

            for(int j=0;j<C;j++)

                cost[i][j]=sc.nextInt();

        System.out.print(minCost(cost, 2, 2));

input:

3 3

1 2 3

4 8 2

1 5 3

output:

Java program to find the minimum cost to reach from 0 to N in an integer

import java.util.*;

public class Hello {

static int minCost(int N, int P, int Q)

    int cost = 0;

    while (N > 0) {

        if ((N & 1)>0) {

            cost += P;

            N--;

        else {

            int temp = N / 2;

            if (temp * P > Q)

                cost += Q;

            else

                cost += P * temp;

            N /= 2;

    return cost;

public static void main(String[] args)

    Scanner sc=new Scanner(System.in);

    int N=sc.nextInt();

    int P=sc.nextInt();

    int Q=sc.nextInt();

    System.out.println(minCost(N, P, Q));

input:

5 2 3

output:

explanation:

here N=5,P=2,Q=3

-to incement from 0 to 1, there is a cost of 2.

-to increment from 1 to 2, there is a cost of 2(doubline cost is 3 so we just increment 1 to 2 which attracys only a cost of 2).

-to double from 2 to 4, there is a cost of 2.

-to increment from 4 to 5, there is a cost of 2.

hence total minimum cost is 2+2+3+2=9.

input:

4 1 5

output:

Java program to collect the maximum points in a matrix

import java.uti.*;

class Main

public static int max(int a,int b)

    return (a>b)?a:b;

public static void main(String[] args)

Scanner sc=new Scanner(System.in);

int R=sc.nextInt();

int C=sc.nextInt();

int[][] mat=new int[100][100];

int[][] ans=new int[100][100];

for(int i=0;i<R;i++)

    for(int j=0;j<C;j++)

        mat[i][j]=sc.nextInt();

int k=0;

for(int i=0;i<C;i++)

    ans[i][0]=mat[i][k];

int maxv=0;

for(int j=1;j<C;j++)

    for(int i=0;i<R;i++)

        if(i==0)

            ans[i][j]=max(ans[i][j-1],ans[i+1][j-1])+mat[i][j];

        else if(i==R-1)

            ans[i][j]=max(ans[i][j-1],ans[i-1][j-1])+mat[i][j];

        else

            ans[i][j]=max(ans[i][j-1],max(ans[i-1][j-1],ans[i+1][j-1]))+mat[i][j];

        if(j==C-1&&(ans[i][j]>maxv))

            maxv=ans[i][j];

System.out.print(maxv);

input:

3 3

5 3 3

2 1 4

0 9 4

output:

input:

4 4

1 3 1 1

2 2 4 1

5 0 2 3

0 6 1 2

output:

input:

10 10

80 32 29 39 0 13 88 12 89 96

48 72 47 55 49 79 7 74 65 33

48 76 89 60 81 31 47 79 48 6

17 24 78 28 79 46 31 45 74 9

92 85 85 8 68 32 56 40 80 93

58 41 35 43 86 46 32 98 33 48

100 13 5 60 27 65 98 84 85 75

11 66 22 96 86 97 64 47 54 10

44 40 93 11 21 83 82 39 7 49

59 33 80 28 55 55 37 59 99 42

output:

input:

4 4

1 3 1 7

2 2 4 1

5 0 2 3

0 8 1 2

output:

Java program to find the minimum weight in the cart (Jhony's ammusement park)

import java.util.*;

class Main

static int max(int a,int b)

    return (a>b)?a:b;

static int min(int a,int b)

    return (a<b)?a:b;

public static void main(String[] args)

Scanner sc=new Scanner(System.in);

int N=sc.nextInt();

int[][] matrix=new int[N][N];

for(int row=0;row<N;row++)

    for(int col=0;col<N;col++)

        &matrix[row][col]=sc.nextInt();

int[][] weight=new int[N][N];

//fill the top left corner

weight[0][0]=matrix[0][0];

//fill the first row

for(int row=1;row<N;row++)

    weight[row][0]=max(matrix[row][0],weight[row-1][0]);

//fill the first column

for(int col=1;col<N;col++)

     weight[0][col]=max(matrix[0][col],weight[0][col-1]);

//fill the remaining part of the matrix

for(int row=1;row<N;row++)

    for(int col=1;col<N;col++)

        int min_weight=min(weight[row][col-1],weight[row-1][col]);

        //col-1  --> leftside ; //row-1  --> top side;

        weight[row][col]=max(min_weight,matrix[row][col]);

System.out.print(weight[N-1][N-1]);

Java program to find the ugly number of the given number

import java.util.*;

class Main {

    static int maxDivide(int a, int b)

        while(a % b == 0)

            a = a/b;

        return a;

    static int isUgly(int no)

        no = maxDivide(no, 2);

        no = maxDivide(no, 3);

        no = maxDivide(no, 5);

        return (no == 1)? 1 : 0;

    static int getNthUglyNo(int n)

        int i = 1;

        int count = 1;

        while(n > count)

            i++;

            if(isUgly(i) == 1)

                count++;

        return i;

    public static void main(String args[])

        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();

        int no = getNthUglyNo(N);

        System.out.println("150th ugly "+"no. is "+ no);

Input  : N = 7

Output : 8

Input  : N = 10

Output : 12

Input  : N = 15

Output : 24

Input  : N = 150

Output : 5832

Java program to find the Nth term in fibonacci series

import java.util.*;

class Main

    static int fib(int n)

    if (n <= 1)

       return n;

    return fib(n-1) + fib(n-2);

    public static void main (String args[])

     Scanner sc=new Scanner(System.in);

    int n = sc.nextInt();

    System.out.println(fib(n));

Input  : n = 2

Output : 1

Input  : n = 9

Output : 34

Java program to find the Nth catalan number using binomial coefficient method

import java.util.*;

class Main {

    static long binomialCoeff(int n, int k) {

        long res = 1;

        if (k > n - k) {

            k = n - k;

        for (int i = 0; i < k; ++i) {

            res *= (n - i);

            res /= (i + 1);

        return res;

    static long catalan(int n)

        long c = binomialCoeff(2 * n, n);

        return c / (n + 1);

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();

        for (int i = 0; i < N; i++) {

            System.out.print(catalan(i) + " ");

input:

output:

1 1 2 5 14 42 132 429 1430 4862

explanation:

We can also use below formula to find nth catalan number in O(n) time.

C_n = (2n)! / ((n + 1)!n!)

Java program to count number of ways to partition a set into K subsets

import java.util.*;

class GFG

    public static int countP(int n, int k)

       if (n == 0 || k == 0 || k > n)

          return 0;

       if (k == 1 || k == n)

          return 1;

       return (k * countP(n - 1, k)

              + countP(n - 1, k - 1));

    public static void main(String args[])

       Scanner sc=new Scanner(System.in)

       int N=sc.nextInt();

       int K=sc.nextInt();

       System.out.println(countP(N, K));

Input: n = 3, k = 2

Output: 3

Explanation: Let the set be {1, 2, 3}, we can partition

             it into 2 subsets in following ways

             {{1,2}, {3}},  {{1}, {2,3}},  {{1,3}, {2}}

Input: n = 3, k = 1

Output: 1

Explanation: There is only one way {{1, 2, 3}}

Java program to find the size of submatrix which contains all 1's

import java.util.*;

public class Hello {

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        int[][] mat=new int[n][n];

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)

                mat[i][j]=sc.nextInt();

        int R=n,C=n;

        int[][] dp=new int[R][C];

        for(int i=0;i<R;i++)

            dp[i][0]=mat[i][0];

        for(int j=0;j<C;j++)

            dp[0][j]=mat[0][j];

        for(int i=1;i<R;i++)

            for(int j=1;j<C;j++)

                if(mat[i][j]==1)

                    dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;

                else{

                    dp[i][j]=0;

        int maxsize=0;

        for(int i=0;i<R;i++)

            for(int j=0;j<C;j++)

                if(maxsize<dp[i][j])

                    maxsize=dp[i][j];

        System.out.print(maxsize*maxsize);

sample input 1:

1 1 0 1

1 1 0 0

0 1 1 1

0 1 0 1

sample output 1:

sample input 2:

1 0 1 1 1 0

1 0 1 1 1 1

0 0 1 1 1 0

1 0 1 0 1 1

0 0 1 0 1 0

1 0 1 1 1 0

sample output 2:

Find the Length of Longest Anagram Sequence in two strings

import java.util.*;

public class Main

    public static int findCount(String str1,String str2)

        int l1=str1.length();

        int l2=str2.length();

        int[] freq1=new int[26];

        int[] freq2=new int[26];

        Arrays.fill(freq1,0);

        Arrays.fill(freq2,0);

        for(int index1=0;index1<l1;index1++)

            freq1[str1.charAt(index1)-'a']++;

        for(int index2=0;index2<l2;index2++)

            freq2[str2.charAt(index2)-'a']++;

        int count=0;

        for(int index=0;index<26;index++)

            count+=Math.min(freq1[index],freq2[index]);

        return count;

    public static void main (String[] args)

        Scanner sc=new Scanner(System.in);

        String str1=sc.next();

        String str2=sc.next();

        System.out.print(findCount(str1,str2));

Input 1:

abdacp

ckamb

Output 1:

Input 2:

abbcfke

fbaafbly

Output 2:

String distance - 2 edits

import java.util.*;

public class Main

    static int editdistance2Edits(String s1,String s2,int m,int n)

        int[][] edit=new int[m+1][n+1];

        for(int index1=0;index1<=m;index1++)

            for(int index2=0;index2<=n;index2++)

                if(index1==0||index2==0)

                edit[index1][index2]=0;

                else if(s1.charAt(index1-1)==s2.charAt(index2-1))

                edit[index1][index2]=edit[index1-1][index2-1]+1;

                else

                edit[index1][index2]=Math.max(edit[index1-1][index2],edit[index1][index2-1]);

        return (m-edit[m][n])+(n-edit[m][n]);

    public static void main (String[] args)

        Scanner sc=new Scanner(System.in);

        String str1=sc.next();

        String str2=sc.next();

        int l1=str1.length();

        int l2=str2.length();

        System.out.print(editdistance2Edits(str1,str2,l1,l2));

input 1:

cat

cut

output 1:

input 2:

sunday

saturday

output 2:

String edit-distance

import java.util.*;

pubic class Main

    static int  editDistance(String s1,String s2,int m,int n)

        int edit[][]=new int[m+1][n+1];

        for(int i=0;i<=m;i++)

            for(int j=0;j<=n;j++)

                if(i==0)

                edit[i][j]=j;

                else if(j==0)

                edit[i][j]=i;

                else if(s1.charAt(i-1)==s2.charAt(j-1))

                edit[i][j]=edit[i-1][j-1];

                else

                edit[i][j]=1+Math.min(Math.min(edit[i-1][j],edit[i][j-1]),edit[i-1][j-1]);

        return edit[m][n];

 public static void main (String[] args)

     Scanner sc=new Scanner(System.in);

     String s1=sc.next();

     String s2=sc.next();

     int m=s1.length();

     int n=s2.length();

     System.out.print(editDistance(s1,s2,m,n));

input 1:

cat

cut

output 1:

input 2:

sunday

saturday

output 2:

Longest Palindromic Substring Length

import java.util.*;

public class Main

    static int longestPalindrome(String str)

        int maxlen=1,start=0,low,high;

        int len=str.length();

        for(int i=1;i<len;++i)

            low=i-1;

            high=i;

            while(low>0&&high<len&&str.charAt(low)==str.charAt(high))

                if(high-low+1>maxlen)

                    start =low;

                    maxlen=high-low+1;

                --low;

                ++high;

            low=i-1;

            high=i+1;

            while(low>=0&&high<len&&str.charAt(low)==str.charAt(high))

                if(high-low+1>maxlen)

                    start=low;

                    maxlen=high-low+1;

                --low;

                ++high;

        return maxlen;

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        String str=sc.nextLine();

        int len=str.length();

        System.out.print("Length of longest palindromic substring is "+longestPalindrome(str));

input 1:

bananas

output 1:

Longest Common Subsequence Length

import java.util.*;

public class Main

    public static int lcs(char[] x,char[] y,int a,int b)

        if(a==0||b==0)

            return 0;

        else if(x[a-1]==y[b-1])

            return 1+lcs(x,y,a-1,b-1);

        else

            return Math.max(lcs(x,y,a-1,b),lcs(x,y,a,b-1));

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        String str1=sc.next();

        String str2=sc.next();

        char[] x=str1.toCharArray();

        char[] y=str2.toCharArray();

        System.out.print("LCS length is "+lcs(x,y,str1.length(),str2.length()));

Input 1:

AGGTAB

GXTXAYB

Output 1:

LCS length is 4

Minimum deletions to form a palindrome

import java.util.*;

public class Main

    static int findMindeletion(char str[],int x,int y)

        if(x>y)

            return x;

        else if(x==y)

            return 0;

        else if(x==y-1)

            return (str[x]==str[y])?0:1;

        else

            return (str[x]==str[y])?findMindeletion(str,x+1,y-1):(Integer.min(findMindeletion(str,x,y-1),findMindeletion(str,x+1,y))+1);

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        System.out.println("Enter the String:");

        String str=sc.nextLine();

        int n=str.length();

        System.out.print("The minimum number of deletions required are "+findMindeletion(str.toCharArray(),0,n-1));

Input1:

Enter the String:

madm

Output1:

The minimum number of deletions required are 1

Input2:

Enter the String:

welcome

Output2:

The minimum number of deletions required  are 4

Vowel count in Sliding Window:(with o(n) time complexity)

import java.util.*;

public class Main

    static int isVowel(char c)

        if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U')

        return 1;

        else

        return 0;

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();

        String str=sc.next();

        int l=str.length();

        int count=0;

        for(int index=0;index<N;index++)

            if(isVowel(str.charAt(index))==1)

            count++;

        System.out.print(count+" ");

        for(int index=N;index<l;index++)

            count=count-(isVowel(str.charAt(index-N)));

            count=count+(isVowel(str.charAt(index)));

            System.out.print(count+" ");

input 1:

environment

output 1:

2 1 2 2 1 2 1 1

input 2:

SKILLRACK

output 2:

0 1 1 0 0 1 1 0

Sliding Window array sum: (with O(n) time complexity)

import java.util.*;

public class Main

    public static void main(String[] args)

        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();

        int[] arr=new int[N];

        for(int index=0;index<N;index++)

            arr[index]=sc.nextInt();

        int K=sc.nextInt();

        int sum=0;

        for(int index=0;index<K;index++)

            sum=sum+arr[index];

        System.out.print(sum+" ");

        for(int index=K;index<N;index++)

            sum=sum-arr[index-K];

            sum=sum+arr[index];

            System.out.print(sum+" ");

input 1:

5 80 90 5 30 42 4

output 1:

175 175 125 77 76

Robot movement - Maximum possible steps:

import java.util.*;

public class Main

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int N=sc.nextInt();

  int ways=sc.nextInt();

  long[] totalWays=new long[N+1];

  int[] Ways=new int[N+1];

  for(int index=0;index<ways;index++)

      Ways[index]=sc.nextInt();

  totalWays[0]=1;

  for(int step=1;step<=N;step++)

      for(int way=0;way<ways;way++)

          if(step>=Ways[way])

              totalWays[step]+=totalWays[step-Ways[way]];

  System.out.print(totalWays[N]);

input 1:

5 2

2 3

output 1:

input 2:

24 4

2 3 6 5

output 2:

Robot movement - skip Damaged steps:

import java.util.*;

public class Main

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int N=sc.nextInt();

  int ways=sc.nextInt();

  int damage=sc.nextInt();

  long[] totalWays=new long[N+1];

  int[] Ways=new int[N+1];

  List<Integer> Damage=new ArrayList<>();

  for(int index=0;index<ways;index++)

      Ways[index]=sc.nextInt();

  for(int index=1;index<=damage;index++)

      Damage.add(sc.nextInt());

  totalWays[0]=1;

  for(int step=1;step<=N;step++)

      if(Damage.contains(step))

          totalWays[step]=0;

          continue;

      for(int way=0;way<ways;way++)

          if(step>=Ways[way])

              totalWays[step]+=totalWays[step-Ways[way]];

  System.out.print(totalWays[N]);

input 1:

5 2 1

2 3

output 1:

input 2:

18 3 2

2 3 5

4 13

output 2:

Robot Movement - skip slippery step:

import java.util.*;

public class Main

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int N=sc.nextInt();

  int ways=sc.nextInt();

  int slip=sc.nextInt();

  long[] totalWays=new long[N+1];

  totalWays[0]=1;

  int[] Ways=new int[ways+1];

  List<Integer> Slippery=new ArrayList<>();

  for(int way=0;way<ways;way++)

      Ways[way]=sc.nextInt();

  for(int index=1;index<=slip;index++)

      Slippery.add(sc.nextInt());

  for(int step=1;step<=N;step++)

      for(int way=0;way<ways;way++)

          if(step>=Ways[way])

              totalWays[step]+=totalWays[step-Ways[way]];

      if(Slippery.contains(step))

          int lastNonSlippery=step-1;

          while(Slippery.contains(lastNonSlippery)&&lastNonSlippery>0)

              lastNonSlippery--;

          if(lastNonSlippery>0)

              totalWays[lastNonSlippery]+=totalWays[step];

          totalWays[step]=0;

  System.out.print(totalWays[N]);

input 1:

5 2 1

2 3

output 1:

input 1:

18 4 3

3 2 4 6

2 6 12

output 1:

Maximum sum -  non adjacent elements:

import java.util.*;

public class Main

    static int findMaxSum(int[] arr,int n)

        int num1=arr[0],num2=0,ans=0;

        for(int index=1;index<n;index++)

            if(num1>num2)

            ans=num1;

            else

            ans=num2;

            num1=num2+arr[index];

            num2=ans;

        return ((num1>num2)?num1:num2);

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int n=sc.nextInt();

  int[] arr=new int[n];

  for(int index=0;index<n;index++)

      arr[index]=sc.nextInt();

  System.out.print(findMaxSum(arr,n));

input 1:

35 47 27 67 56 1 19 28 8 40

output 1:

input 2:

2 3 4 4 1

output 2:

Maximum sum of subarray :

import java.util.*;

public class Main

    static int maxSubArray(int[] arr)

        int maxSum=arr[0],sum=arr[0];

        for(int index=1;index<arr.length;index++)

            sum=Math.max(arr[index],sum+arr[index]);

            maxSum=Math.max(maxSum,sum);

        return maxSum;

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int n=sc.nextInt();

  int[] arr=new int[n];

  for(int index=0;index<n;index++)

      arr[index]=sc.nextInt();

  System.out.print(maxSubArray(arr));

input 1:

-5 -4 -6

Output 1:

-4

input 2:

5 4 -3 -5 6

output 2:

Longest Common Substring  Length:

import java.util.*;

public class Main

    static int findLCS(String str1,String str2)

        int l1=str1.length();

        int l2=str2.length();

        int[][] dp=new int[l1+1][l2+1];

        int max=0;

        for(int index1=1;index1<=l1;index1++)

            for(int index2=1;index2<=l2;index2++)

                if(str1.charAt(index1-1)==str2.charAt(index2-1))

                    dp[index1][index2]=dp[index1-1][index2-1]+1;

                    if(dp[index1][index2]>max)

                        max=dp[index1][index2];

        return max;

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  String str1=sc.next();

  String str2=sc.next();

  System.out.print(findLCS(str1,str2));

input 1:

nose

raise

output 1:

input 2:

fever

lever

output 2:

Length of longest substring with equal alphabets and digits:

import java.util.*;

public class Main

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  String str=sc.next();

  Map<Integer,Integer> hm=new HashMap<>();

  int max=0,l=str.length(),count=0,position=0;

  hm.put(count,position);

  for(int index1=0;index1<l;index1++)

      position++;

      if(Character.isLetter(str.charAt(index1)))

         count++;

      else if(Character.isDigit(str.charAt(index1)))

          count--;

      if(hm.containsKey(count))

          int currLen=position-hm.get(count);

          if(currLen>max)

          max=currLen;

      else

      hm.put(count,position);

  System.out.print(max);

input 1:

abz23aacc1567

output 1:

input 2:

ab547b63

output 2:

Total Possible Dribbling paths of a basketball player:

import java.util.*;

import java.math.*;

public class Main

    static void setRowValue(BigInteger[][] totalPaths,int C)

        for(int col=0;col<C;col++)

            totalPaths[0][col]=BigInteger.valueOf(1);

    static void setColValue(BigInteger[][] totalPaths,int R)

        for(int row=0;row<R;row++)

            totalPaths[row][0]=BigInteger.valueOf(1);

    static BigInteger findTotalPaths(int R,int C)

        BigInteger[][] totalPaths=new BigInteger[R][C];

        setRowValue(totalPaths,C);

        setColValue(totalPaths,R);

        for(int row=1;row<R;row++)

            for(int col=1;col<C;col++)

                totalPaths[row][col]=totalPaths[row-1][col].add(totalPaths[row][col-1]);

        return totalPaths[R-1][C-1];

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int R=sc.nextInt();

  int C=sc.nextInt();

  System.out.print(findTotalPaths(R,C));

input 1:

2 3

output 1:

input 2:

3 3

output 2:

input 3:

25 21

output 3:

1761039350070

input 4:

100 91

output 4:

36744876179076249096579888358334560698439034159836506900

Collect Maximum points in a matrix:

import java.util.*;

public class Main

    static int findMaxPoints(int[][] mat,int R,int C)

        int[][] points=new int[R][C];

        points[0][0]=mat[0][0];

        for(int row=1;row<R;row++)

            points[row][0]=points[row-1][0]+mat[row][0];

        for(int col=1;col<C;col++)

            points[0][col]=points[0][col-1]+mat[0][col];

        for(int row=1;row<R;row++)

            for(int col=1;col<C;col++)

                points[row][col]=mat[row][col]+Math.max(points[row][col-1],points[row-1][col]);

        return points[R-1][C-1];

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int R=sc.nextInt();

  int C=sc.nextInt();

  int[][] mat=new int[R][C];

  for(int row=0;row<R;row++)

      for(int col=0;col<C;col++)

          mat[row][col]=sc.nextInt();

  System.out.print(findMaxPoints(mat,R,C));

input 1:

4 5

4 2 9 6 1

7 9 6 5 4

5 7 3 8 8

7 4 9 9 4

output 1:

Collect Maximum points from starting point till end:

import java.util.*;

public class Main

    static int findMaxPoints(int[][] mat,int R,int C,int startRow,int startCol)

        int[][] points=new int[R][C];

        points[startRow][startCol]=mat[startRow][startCol];

        for(int row=startRow+1;row<R;row++)

            points[row][startCol]=points[row-1][startCol]+mat[row][startCol];

        for(int col=startCol+1;col<C;col++)

            points[startRow][col]=points[startRow][col-1]+mat[startRow][col];

        for(int row=startRow+1;row<R;row++)

            for(int col=startCol+1;col<C;col++)

                points[row][col]=mat[row][col]+Math.max(points[row][col-1],points[row-1][col]);

        return points[R-1][C-1];

    public static void main(String[] args)

   Scanner sc=new Scanner(System.in);

  int R=sc.nextInt();

  int C=sc.nextInt();

  int[][] mat=new int[R][C];

  for(int row=0;row<R;row++)

      for(int col=0;col<C;col++)

          mat[row][col]=sc.nextInt();

  int startRow=sc.nextInt();

  int startCol=sc.nextInt();

  System.out.print(findMaxPoints(mat,R,C,startRow,startCol));

input 1:

4 5

4 2 9 6 1

7 9 6 5 4

5 7 3 8 8

7 4 9 9 4

0 1

output 1: