You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

class Solution {
    public int uniquePaths(int m, int n) {
        //一维空间，其大小为 n
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                //等式右边的 dp[j]是上一次计算后的，加上左边的dp[j-1]即为当前结果
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }   
}

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

maxweight = 4

items:    weight   value
item0:       1      15
item1:       3      20
item2:       4      30

        0   1   2   3   4   
item0:  0   15  15  15  15       
item1:  0    
item2:  0   

maxweight = 4

items:    weight   value
item0:       1      15
item1:       3      20
item2:       4      30


        0   1   2   3   4   
item0:  0   15  15  15  15       
item1:  0   15  15  20  35   
item2:  0   15  15  20  35 

public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        testWeightBagProblem(weight, value, bagSize);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        int wLen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wLen + 1][bagSize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wLen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wLen; i++){
            for (int j = 1; j <= bagSize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wLen; i++){
            for (int j = 0; j <= bagSize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        testWeightBagProblem(weight, value, bagSize);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        int wLen = weight.length, value0 = 0;
        //定义dp数组：dp[j]表示背包容量为j时，获得的最大价值
        int[] dp = new int[bagSize + 1];
       
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i <= wLen; i++){
        // need reverse iterate
            for (int j = bagSize; j >= weight[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        //打印dp数组
   
            for (int j = 0; j <= bagWeight; j++){
                System.out.print(dp[j] + " ");
            }
    }

maxweight = 4

items:    weight   value
item0:       1      15
item1:       3      20
item2:       4      30


        0   1   2   3   4   
item0:  0   15  15  15  15       
item1:  0   15  15  20  35   
item2:  0   15  15  20  35 



        0   1   2   3   4   
item0:  0   15  15  15  15 

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

This is a Knapsack problem, 

nums[0] 1:   0    1   2   3   4   5   6   7   8   9   10  11
Pint:   <--  0     1                                   1   1

nums[1] 5 :  0    1   2   3   4   5   6   7   8   9   10  11
Pint:   <--  0     1              5   6                 6   6

nums[2] 11:  0    1   2   3   4   5   6   7   8   9   10  11
Pint:   <--  0     1              5   6                6   11

nums[3]  5:  0    1   2   3   4   5   6   7   8   9   10  11
Pint:   <--  0     1              5   6                10   11

// i = 0, the first item
if (nums[0] <= target) {
    dp[0][nums[0]] = 0;
}

for (int i = 1; i < len; i++) {
    for (int j = 0; j <= target; j++) {
       
    }
}

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.

 int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

int len = strs.length;
int[][][] dp = new int[len + 1][m + 1][n + 1];

for (int i = 1; i <= len; i++) {
    int[] count = countZeroAndOne(Strs[i - 1]);
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= n; j++) {
            dp[i][j][k] =  dp[i - 1][j][k];
            int zeros = count[0];
            int ones = count[1];
            if (j >= zeros && k >= ones) {
                dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones]);
            }
    }
}
return dp[len][m][n];
}

private int[] countZeroAndOne(String str) {
    int[] cnt = new int[2];
    for (char c : str.toCharArray()) {
        cnt[c - '0']++;
    }
    return cnt;
}

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

for (int i = 0; i <= target; i++) {
   for (int j = 0; j <= nums.length; j++) { 
       if (i > nums[j]) {
           dp[i] += dp[i - nums[j]];
       }
   }
}
return dp[target];

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 , 3 ---- to m steps. In how many distinct ways can you climb to the top?

int[] dp = new int[n + 1];
int[] weight = {1, 2};
dp[0] = 1;

for (int i = 0; i <= n; i++) {
   for (int j = 0; j <= weight.length; j++) { 
       if (i > weight[j]) {
           dp[i] += dp[i - weight[j]];
       }
   }
}
return dp[n];

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

            3{6, 7}
        /       \
      2{3, 2}      3{1, 3}
        \           \
        3{0, 3}      1{}

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

            3{6, 7}
        /       \
      2{3, 2}      3{1, 3}
        \           \
        3{0, 3}      1{}

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

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

       dp[i][0]  dp[i][1]
        -7          0
        -1          0
        -1          4
        -1          4
        -1          5
        -1          5

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

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

       dp[i][0]  dp[i][1]
    

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

       [1, 2, 3, 4, 5]
i   j       0   1   2   3   4

0          0   -1   0   -1  0
1          0   -1   1   -1  1
2          0   -1   2   -1  2
3          0   -1   3   -1  3
4          0   -1   4   -1  4
       

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

for (int j = 0; j < 2 * k -1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

for (int j = 1; j < 2 * k -1; j += 2) {
    dp[0][j] = - prices[0];
}

       [1, 2, 3, 4, 5]
i   j       0   1   2   3   4

0          0   -1   0   -1  0
1          0   -1   1   -1  1
2          0   -1   2   -1  2
3          0   -1   3   -1  3
4          0   -1   4   -1  4
       

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

dp[i][0] = max( dp[i - 1][0], max(dp[i][3] - prices[i], dp[i][1] - prices[i]));
dp[i][1] = max( dp[i - 1][1], dp[i -1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];

       [1, 2, 3, 0, 2]
i   j       0   1   2   3   

0          -1   0   0    0  
1          -1   0   1    0  
2          -1   0   2    1  
3           1   1  -1    2  
4           1   2   3    -1  
       

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

for (int i = 1; i <= A.length(); i++) {
    for (int j = 1; j <= B.length(); j++) {
        if (A[i -1] == B[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > res) res = dp[i][j];
}

    A:  [1, 2, 3, 2, 1]     B:  [3, 2, 1, 4, 7]

   B:       3   2   1   4   7   
        0   0   0   0   0   0
1       0   0   0   1   0   0   
2       0   0   1   0   0   0   
3       0   1   0   0   0   0   
2       0   0   2   0   0   0      
1       0   0   0   3   0   0      
       

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

    A:  "abcde"    B:  "ace"

   B:       a   c   e    
        0   0   0   0   
a       0   1   1   1   
b       0   1   1   1       
c       0   1   2   2    
d       0   1   2   2       
e       0   1   2   3       
       

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

    A:  "abcde"    B:  "ace"

   B:       a   c   e    
        0   0   0   0   
a       0   1   1   1   
b       0   1   1   1       
c       0   1   2   2    
d       0   1   2   2       
e       0   1   2   3       
       

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

    A:  "ahbgdc"    B:  "abc"

   B:       a   h   b   g   d   c       
        0   0   0   0   0   0   0    
a       0   1   1   1   1   1   1
b       0   0   0   2   2   2   2 
c       0   0   0   0   0   0   3 
    
       

Given two strings s and t, return the number of distinct subsequences of s which equals t.

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

The test cases are generated so that the answer fits on a 32-bit signed integer.

    A:  "baegg"    B:  "bag"

   B:       b   a   g     
        1   0   0   0  
b       1   1   0   0   
a       1   1   1   0   
e       1   1   1   0
g       1   1   1   1
g       1   1   1   2     
    
       

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

    A:  "sea"    B:  "eat"

   B:       e   a   t     
        0   1   2   3  
s       1   2   3   4   
e       2   1   2   3   
a       3   2   1   2       

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

    A:  "horse"    B:  "ros"

   B:       r   o   s     
        0   1   2   3  
h       1   1   2   3   
o       2   2   1   2   
r       3   2   2   2  
s       4   3   3   2  
e       5   4   4   3               

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

    A:  "aaa"   

      
        1   1   1     
        0   1   1      
        0   0   1      
              

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

    A:  "cbbd"   

        c   b   b   d
   c    1   1   2   2     
   b    0   1   2   2      
   b    0   0   1   1  
   d    0   0   0   1   

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

   

                        dp
       2                2
       3   4            5
       6   5   7        10
       4   1   8   3    11

if (triangle == null || triangle.size() == 0) {
            return 0;
        }
    int row = triangle.size();
    int column = triangle.get(row - 1).size();

    int[][] dp = new int[row][column];
    dp[0][0] = triangle.get(0).get(0);
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
    }
    for (int i = 1; i < n; i++) {
        int j = 1;
        while (j < triangle.get(i).size() - 1) {
            dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            j++;
        }
        dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
    }

    return Arrays.stream(dp[n - 1]).min().getAsInt();

       2                
       3   4             
       6   5   7         
       4   1   8   3                              

       2                
       3   4             
       6   5   7         
       4   1   8   3 
       0   0   0   0    0                     

       2                
       3   4             
       7   6   10         
       4   1   8   3 
       0   0   0   0    0                     

       2                
       9   10             
       7   6   10         
       4   1   8   3 
    
```java
```java                        
       11                
       9   10             
       7   6   10         
       4   1   8   3    
```java

if (triangle == null || triangle.size() == 0) {
            return 0;
        }
    int n = triangle.size();

    int[][] dp = new int[n + 1][n + 1];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = Math.min(dp[i + 1][j + 1], dp[i + 1][j])+ triangle.get(i).get(j);
    }

    return dp[0][0];

       2                
       3   4             
       6   5   7         
       4   1   8   3                              

if (triangle == null || triangle.size() == 0) {
            return 0;
        }
    int row = triangle.size();
    int column = triangle.get(row - 1).size();

    int[] dp = new int[column + 1];

    for (int i = row - 1; i >= 0; i--) {
        for (int j = 0; j < triangle.get(i).size(); j++) {
            dp[j] = Math.min(dp[j + 1], dp[j])+ triangle.get(i).get(j);
    }

    return dp[0];

    int row = triangle.size();
    
    int[] dp = new int[row + 1];

    for (int i = row - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j + 1], dp[j])+ triangle.get(i).get(j);
    }

    return dp[0];

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

   

                        dp
       2                2
       3   4            5
       6   5   7        10
       4   1   8   3    11

int m = matrix.length;
int n = matrix[0].length;
int[] dp= new int[n + 2];
dp[0] = dp[n + 1] = Integer.MAX_VALUE;

for (int i = m - 1; i >= 0; i--) {
    int tmp = 0, last = Integer.MAX_VALUE;
    for (int j = 1; j <= n; j++) {
        tmp = dp[j];
        dp[j] = Math.min(dp[j], Math.min(last, dp[j + 1])) + matrix[i][j - 1];
        last = tmp;
    }
}
  
int min = Integer.MAX_VALUE;
for (int j = 1; j <=  n; j++) {
    min = Math.min(min, dp[j]);
}
return min;

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 109 + 7.

int mod = 1000000007;
public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // initiation

        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, end, fuel);
    }

int dfs(int[] ls, int u, int end, int fuel) {
        // if cache alread has the answer, return
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }

        int n = ls.length;
         // base case 1：if the fuel is 0,
        if (fuel == 0 && u != end) {
            cache[u][fuel] = 0;
            return 0;
        } 

        // base case 2
        boolean hasNext = false;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[u] - ls[i]);    
                if (fuel >= need) {
                    hasNext = true;
                    break;
                }
            }
        }
        if (fuel != 0 && !hasNext) {
            int a= cache[u][fuel] = u==end?1:0;
            return a;
        }

        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
        

int mod = 1000000007;
public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // initiation

        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, end, fuel);
    }

int dfs(int[] ls, int u, int end, int fuel) {
        // if cache alread has the answer, return
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }

        int n = ls.length;
        
        int need = Math.abs(ls[u] - ls[end]);
        if (need > fuel) {
            cache[u][fuel] = 0;
            return 0;
        }

        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
        

int mod = 1000000007;
public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        int[][] dp = new int[n][fuel + 1];

        // start = end
        for (int i = 0; i <= fuel; i++) {
            dp[end][i] = 1;
        }

        for (int cur = 0; cur <= fuel; cur++) {
            for (int i = 0; i < n; i++) {
                for (int k= 0; k < n; k++) {
                    if (i != k) {
                        int need =  Math.abs(ls[i] - ls[u]);
                        if (cur >= need) {
                            dp[i][cur] += dp[k][cur - need];
                            dp[i][cur] %= mod;
                        }
                    }
                }
            }
        }

        
        return dp[start][fuel];
    }
        

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

                        
       1    2   3
       4    5   6
       7    8   9

                        
i - 1               i1          i2
      
i           i1  i1  i2  i1  i1  i1  i1 i1