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?
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
Example 3:
Input: m = 7, n = 3
Output: 28
Example 4:
Input: m = 3, n = 3
Output: 6
Constraints:
- 1 <= m, n <= 100
- It's guaranteed that the answer will be less than or equal to 2 * 109.
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m+1][n+1];
dp[1][1] = 1;
for(int j=2;j<=n;j++){
dp[1][j] = dp[1][j-1];
}
for(int i=2;i<=m;i++){
dp[i][1] = dp[i-1][1];
}
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
dp[i][j] = dp[i][j-1]+dp[i-1][j];
}
}
return dp[m][n];
}
}题目
给定MxN棋盘，只允许从左上往右下走，每次走一格。共有多少种走法？
思路
Matrix DP（二维DP） 问题
- 初始化
预处理第一个row： dp[0][j] = 1 因为从左上起点出发，往右走的每一个unique path都是1
预处理第一个col： dp[i][0]= 1 因为从左上起点出发，往下走的每一个unique path 都是1
- 转移方程
因为要求所有possible unique paths之和
dp[i][j] 要么来自dp[i-1][j] 要么来自dp[i][j-1]
插入排序
public class Sort {
public static void main(String[] args) {
Sort sort = new Sort();
System.out.println("sort:");
int[] a = new int[]{1, 8, 2, 9, 6, 7, 5, 0, 4, 3};
sort.insertSort(a);
System.out.println(Arrays.toString(a));
}
public void insertSort(int[] a) {
int temp = 0;
for(int i=1;i<a.length;i++){
// 需要从i前面已经排好序（从小到大）的数字中插入
int j = i - 1;
// temp赋值给当前的a[i]
temp = a[i];
// 如果j>=0并且a[j]>temp，说明当前的数字比前面的小
for(;j>=0&&a[j]>temp;j--){
// 将前面的数字往后移动一位
a[j+1] = a[j];
}
// 最前面空出来的数字位置，插入当前的temp
a[j + 1] = temp;
}
}
}