DP good questions

(1) Maximal Rectangle (leetcode 85)
(2) Decode ways (leetcode 91)
(3) word break (leetcode 140) what if return one result. Similar, palindrome partition
(4) ugly number (leetcode 264)
(5) longest increasing sub-sequence (leetcode 300)
(6)Create max number(leetcode 321)
(7)Best time to buy and sell stock with cooldown(leetcode 309)
(8)Best time to buy and sell stock IV (leetcode 188)
(9)Maximum subarray III (lintcode 43)
(10) Minimum Adjust cost (lintcode 91)
(11) Backpack (lintcode 92), backpack II (lintcode 125)
(12) coins in a line II (lintcode 395)
(13) K - sum (lint code 89)
(14) Copy books (lintcode 437)
(15) Coins (cc189, 8.11, page 136)

Leetcode 279 Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution 1: Use DP, O(n^3/2) solution

 public class Solution {  
   public int numSquares(int n) {  
     if (n<=0) return 0;  
     int[] dp=new int[n+1];  
     Arrays.fill(dp,Integer.MAX_VALUE);  
     for (int i=0; i<=n; i++) {  
       if (i==0) dp[i]=0;  
       else {  
         for (int j=1; j*j<=i; j++) {  
           dp[i]=Math.min(dp[i],1+dp[i-j*j]);  
         }  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 276 Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Solution 1: DP question. Maintain an array of same and diff. Transaction formula will be same[i]=diff[i-1]; diff[i]=(same[i-1]+diff[i-1])*(n-1). Optimize to O(1) space as below:

 public class Solution {  
   public int numWays(int n, int k) {  
     if (n==0) return 0;  
     int same=0, diff=k;  
     for (int i=1; i<n; i++) {  
       int pre=same;  
       same=diff;  
       diff=(pre+diff)*(k-1);  
     }  
     return same+diff;  
   }  
 }  

Leetcode 265 Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

Solution 1: a DP question. Can be solved with O(k) space and O(nk) time.

 public class Solution {  
   public int minCostII(int[][] costs) {  
     int n=costs.length;  
     if (n==0) return 0;  
     int k=costs[0].length;  
     //if (k<2) return 0;// n==1 and k==1 still works  
     int[] dp=new int[k];  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         for (int j=0; j<k; j++) dp[j]=costs[i][j];  
       }  
       else {  
         int m1=-1, m2=-1, v1=Integer.MAX_VALUE, v2=Integer.MAX_VALUE;  
         for (int j=0; j<k; j++) {  
           if (dp[j]<=v1) {  
             m2=m1;  
             m1=j;  
             v2=v1;  
             v1=dp[j];  
           }  
           else if (dp[j]<=v2) {  
             m2=j;  
             v2=dp[j];  
           }  
         }  
         for (int j=0; j<k; j++) dp[j]=costs[i][j]+((j==m1)?v2:v1);  
       }  
     }  
     int res=Integer.MAX_VALUE;  
     for (int j=0; j<k; j++) res=Math.min(res,dp[j]);  
     return res;  
   }  
 }  

Leetcode 256 Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Solution 1: simple DP

 public class Solution {  
   public int minCost(int[][] costs) {  
     int n=costs.length;  
     int red=0, blue=0, green=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         red=costs[i][0];  
         blue=costs[i][1];  
         green=costs[i][2];  
       }  
       else {  
         int nextRed=costs[i][0]+Math.min(blue,green);  
         int nextBlue=costs[i][1]+Math.min(red,green);  
         green=costs[i][2]+Math.min(red,blue);  
         red=nextRed;  
         blue=nextBlue;  
       }  
     }  
     return Math.min(red,Math.min(blue,green));  
   }  
 }  

Leetcode 221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.
Solution 1: Use DP. dp[i][j] is the max length if matrix[i][j] is the bottom right corner of the square. (1) if matrix[i][j] is 0, dp[i][j]=0; (2) if matrix[i][j]=1, we need to check dp[i-1][j] and dp[i][j-1]; (2a) if they are different, it is smaller of the two plus 1. (2b) check if they are equal, say dp[i-1][j]=dp[i][j-1]=len, check if weather dp[i-len][j-len] is 0 or 1.

 public class Solution {  
   public int maximalSquare(char[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return 0;  
     int n=matrix[0].length;  
     int[] dp=new int[n];  
     int res=0;  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (matrix[i][j]=='0') dp[j]=0;  
         else if (i==0 || j==0) dp[j]=1;  
         else if (dp[j]==dp[j-1]) {  
           int k=dp[j];  
           dp[j]=(matrix[i-k][j-k]=='0')?k:k+1;  
         }  
         else dp[j]=1+Math.min(dp[j-1],dp[j]);  
         res=Math.max(res,dp[j]);  
       }  
     }  
     return res*res;  
   }  
 }  

Leetcode 213 House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution 1: 0 or n-1, one of them must not be robbed. Use DP and House Robber I solution to calculate [0..n-2] and [1...n-1] then get the max of the two.

 public class Solution {  
   public int rob(int[] nums) {  
     int n=nums.length;  
     if (n==0) return 0;  
     if (n==1) return nums[0];  
     return Math.max(rob(nums,0,n-2),rob(nums,1,n-1));  
   }  
   private int rob(int[] nums, int lo, int hi) {  
     int a=0, b=0;// a rob it, b not rot it  
     for (int i=lo; i<=hi; i++) {  
       if (i==lo) {  
         a=nums[i];  
       }  
       else {  
         int aNext=b+nums[i];  
         b=Math.max(a,b);  
         a=aNext;  
       }  
     }  
     return Math.max(a,b);  
   }  
 }  

Leetcode 198 House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution 1:  Use DP to record of current max value of rob this one and noRob this one 

 public class Solution {  
   public int rob(int[] nums) {  
     int n=nums.length;  
     if (n==0) return 0;  
     int rob=0;  
     int notRob=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         rob=nums[i];  
         notRob=0;  
       }  
       else {  
         int temp=Math.max(rob,notRob);  
         rob=notRob+nums[i];  
         notRob=temp;  
       }  
     }  
     return Math.max(rob,notRob);  
   }  
 }  

Leetcode 188 Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution 1: Use DP, local[i][j] is the max value sell at jth using i transaction. globe[i][j] is global best solution. No need to sell at day j. Space can be optimized to O(k). Also, if k>n/2 can apply fast calculation which is O(n) instead of O(n*k).

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     int n=prices.length;  
     if (k>n/2) return quickSolve(prices);  
     int[] local=new int[k+1];  
     int[] globe=new int[k+1];  
     for (int j=1; j<n; j++) {  
       int pre=0;  
       for (int i=1; i<=k; i++) {  
         int temp=globe[i];  
         local[i]=Math.max(pre,local[i]+prices[j]-prices[j-1]);  
         globe[i]=Math.max(globe[i],local[i]);  
         pre=temp;  
       }  
     }  
     return globe[k];  
   }  
   private int quickSolve(int[] prices) {  
     int res=0;  
     for (int i=1; i<prices.length; i++)  
       if (prices[i]>prices[i-1]) res+=prices[i]-prices[i-1];  
     return res;  
   }  
 }  

Leetcode 174 Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution 1: Use DP, the key is start from right bottom and go back to left top.

 public class Solution {  
   public int calculateMinimumHP(int[][] dungeon) {  
     int m=dungeon.length;  
     if (m==0) return 1;  
     int n=dungeon[0].length;  
     if (n==0) return 1;  
     int[] dp=new int[n];  
     for (int i=m-1; i>=0; i--) {  
       for (int j=n-1; j>=0; j--) {  
         if (i==m-1) {  
           if (j==n-1) dp[j]=Math.max(1,1-dungeon[i][j]);  
           else dp[j]=Math.max(1,dp[j+1]-dungeon[i][j]);  
         }  
         else if (j==n-1) dp[j]=Math.max(1,dp[j]-dungeon[i][j]);  
         else dp[j]=Math.max(1,Math.min(dp[j],dp[j+1])-dungeon[i][j]);  
       }  
     }  
     return dp[0];  
   }  
 }  

Leetcode 152 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution 1: Use DP and optimize the space to O(1), keep both max and min product, sometimes negtive number mult

 public class Solution {  
   public int maxProduct(int[] nums) {  
     int n=nums.length;  
     int max=0, min=0, res=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         max=nums[i];  
         min=nums[i];  
         res=nums[i];  
       }  
       else {  
         int maxNew=Math.max(nums[i],Math.max(nums[i]*max,nums[i]*min));  
         min=Math.min(nums[i],Math.min(nums[i]*max,nums[i]*min));  
         max=maxNew;  
         res=Math.max(res,max);  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 140 Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution 1: first use DP to build up if [i...j] is in dict or not, then use DFS to collect all the possible breaks. The thing is to make judgement first, only if there is solution then dfs.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> wordDict) {  
     char[] c=s.toCharArray();  
     int n=c.length;  
     boolean[][] dp=new boolean[n][n];  
     boolean[] exist=new boolean[n+1];  
     List<String> res=new ArrayList<>();  
     List<String> one=new ArrayList<>();  
     if (n==0) return res;  
     exist[0]=true;  
     for (int j=0; j<n; j++){  
       exist[j+1]=false;  
       for (int i=0; i<=j; i++) {  
         dp[i][j]=wordDict.contains(new String(c,i,j-i+1))?true:false;  
         if (dp[i][j] && exist[i]) exist[j+1]=true;  
       }  
     }  
     if (exist[n]) dfs(c,dp,0,one,res);  
     return res;  
   }  
   private void dfs(char[] c, boolean[][] dp, int d, List<String> one, List<String> res) {  
     if (d==c.length) {  
       StringBuilder sb=new StringBuilder();  
       for (String s:one) {  
         sb.append(s);  
         sb.append(' ');  
       }  
       res.add(sb.substring(0,sb.length()-1));  
     }  
     else {  
       for (int i=d; i<c.length; i++) {  
         if (dp[d][i]) {  
           one.add(new String(c,d,i-d+1));  
           dfs(c,dp,i+1,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }  

Leetcode 139 Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution 1: Use DP, dp[i] stores if [0...i] can be break or not.

 public class Solution {  
   public boolean wordBreak(String s, Set<String> wordDict) {  
     int n=s.length();  
     if (n==0) return true;  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=n; i++) {  
       if (i==0) dp[i]=true;  
       else {  
         dp[i]=false;  
         for (int j=0; j<i; j++) {  
           if (dp[j] && wordDict.contains(s.substring(j,i))) {  
             dp[i]=true;  
             break;  
           }  
         }  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 132 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution 1: Use DP. dp[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j]. In the loop, keep update dp[i][j] matrix and res[j] array. The complexity is O(N^2).

 public class Solution {  
   public int minCut(String s) {  
     int n=s.length();  
     char[] c=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];  
     int[] res=new int[n];  
     for (int j=0; j<n; j++) {  
       res[j]=Integer.MAX_VALUE;  
       for (int i=j; i>=0; i--) {  
         dp[i][j]=i==j || (c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]));  
         if (dp[i][j]) {  
           int cut=(i==0)?0:res[i-1]+1;  
           res[j]=Math.min(res[j],cut);  
         }  
       }  
     }  
     return res[n-1];  
   }  
 }  

Leetcode 131 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution 1: DP + DFS: use DP to store if s[i..j] is palindrome or not. This  will guarantee to be O(N^2) complexity.

 public class Solution {  
   public List<List<String>> partition(String s) {  
     int n=s.length();  
     char c[]=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];//store if s[i..j] is palin or not  
     for (int j=0; j<n; j++) {  
       for (int i=j; i>=0; i--) {  
         if (j==i) dp[i][j]=true;  
         else dp[i][j]=c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]);  
       }  
     }  
     List<String> one=new ArrayList<>();  
     List<List<String>> res=new ArrayList<>();  
     dfs(c,0,dp,one,res);  
     return res;  
   }  
   private void dfs(char[] c, int d, boolean[][] dp, List<String> one, List<List<String>> res) {  
     if (d==c.length) res.add(new ArrayList<String>(one));  
     else {  
       for (int j=d; j<c.length; j++) {  
         if (dp[d][j]) {  
           one.add(new String(c,d,j-d+1));  
           dfs(c,j+1,dp,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }  

Leetcode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution 1: Use 2 DP arrays, dp1[i] is max profit of [0...i] and dp2[i] is max profit of [i..n-1], then it is convert to one transaction problem.

 public class Solution {  
   public int maxProfit(int[] prices) {  
     int n=prices.length;  
     int[] dp1=new int[n];  
     int[] dp2=new int[n];  
     int profit=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         profit=0;  
         dp1[i]=0;  
       }  
       else {  
         profit=Math.max(0,profit+prices[i]-prices[i-1]);  
         dp1[i]=Math.max(dp1[i-1],profit);  
       }  
     }  
     for (int i=n-1; i>=0; i--) {  
       if (i==n-1) {  
         profit=0;  
         dp2[i]=0;  
       }  
       else {  
         profit=Math.max(0,profit+prices[i+1]-prices[i]);  
         dp2[i]=Math.max(dp2[i+1],profit);  
       }  
     }  
     int res=0;  
     for (int i=0; i<n; i++) res=Math.max(res,dp1[i]+dp2[i]);  
     return res;  
   }  
 }  

Leetcode 121 Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution 1: Use DP. dp[i] is max profit if sell at day i. Optimize space to O(n).

 public class Solution {  
   public int maxProfit(int[] prices) {  
     int dp=0, max=0;  
     for (int i=0; i<prices.length; i++) {  
       if (i==0) dp=0;  
       else dp=Math.max(0,dp+prices[i]-prices[i-1]);  
       max=Math.max(max,dp);  
     }  
     return max;  
   }  
 }  

Leetcode 120 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution 1: simple DP question. optimize the space to O(n).

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     int n=triangle.size();  
     int[] dp=new int[n];  
     for (int i=0; i<n; i++) {  
       int pre=0;  
       for (int j=0; j<=i; j++) {  
         int temp=dp[j];  
         if (i==0) dp[j]=triangle.get(i).get(j);  
         else {  
           int min=Integer.MAX_VALUE;  
           if (j-1>=0) min=pre;  
           if (j<=i-1 && dp[j]<min) min=dp[j];  
           dp[j]=min+triangle.get(i).get(j);  
         }  
         pre=temp;  
       }  
     }  
     int res=Integer.MAX_VALUE;  
     for (int i=0; i<n; i++) res=Math.min(res,dp[i]);  
     return res;  
   }  
 }  

Leetcode 115 Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution 1: Use DP, two cases: (1) c[i]==c[j]; (2) c[i]!=c[j];

 public class Solution {  
   public int numDistinct(String s, String t) {  
     int m=s.length();  
     int n=t.length();  
     int[][] dp=new int[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (j==0) dp[i][j]=1;  
         else if (i==0) dp[i][j]=0;  
         else if (s.charAt(i-1)==t.charAt(j-1)) dp[i][j]=dp[i-1][j]+dp[i-1][j-1];  
         else dp[i][j]=dp[i-1][j];  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Solution 2: optimize space to O(n)

 public class Solution {  
   public int numDistinct(String s, String t) {  
     int m=s.length();  
     int n=t.length();  
     int[] dp=new int[n+1];  
     for (int i=0; i<=m; i++) {  
       int pre=0;  
       for (int j=0; j<=n; j++) {  
         int temp=dp[j];  
         if (j==0) dp[j]=1;  
         else if (i==0) dp[j]=0;  
         else if (s.charAt(i-1)==t.charAt(j-1)) dp[j]=dp[j]+pre;  
         //else dp[j]=dp[j];  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 97 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution 1: Use DP, dp[i][j] store the result of s1[0...i) s2[0..j) and s3[0...i+j) is interleaving or not. There will be 2 case, s1.charAt(i-1)==s3.charAt(i+j-1) or s2.charAt(j-1)==s3.charAt(i+j-1). Details below:

 public class Solution {  
   public boolean isInterleave(String s1, String s2, String s3) {  
     int m=s1.length();  
     int n=s2.length();  
     if (m+n!=s3.length()) return false;  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else dp[j]=s2.charAt(j-1)==s3.charAt(j-1) && dp[j-1];  
         }  
         else if (j==0) dp[j]=s1.charAt(i-1)==s3.charAt(i-1) && dp[j];  
         else dp[j]=(s1.charAt(i-1)==s3.charAt(i+j-1) && dp[j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && dp[j-1]);  
       }  
     }  
     return dp[n];  
   }  
 }