思路:
state: f[i][j]表示从起点到i,j的最短路径和
function: f[i][j] = min(f[i-1][j], f[i][j-1]) + cost[i][j]
initialize: f[0][0] = cost[0][0], f[0][i] = cost[0][i] + f[0][i-1], f[i][0] = cost[i][0] + f[i-1][0]
answer: f[m-1][n-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
public class { public int minPathSum (int [][] grid) { int m = grid.length; int n = grid[0 ].length; int [][] sum = new int [m][n]; sum[0 ][0 ] = grid[0 ][0 ]; for (int i = 1 ; i < n; i++) { sum[0 ][i] = grid[0 ][i] + sum[0 ][i - 1 ]; } for (int i = 1 ; i < m; i++) { sum[i][0 ] = grid[i][0 ] + sum[i - 1 ][0 ]; } for (int i = 1 ; i < m; i++) { for (int j = 1 ; j < n; j++) { sum[i][j] = grid[i][j] + Math.min(sum[i - 1 ][j], sum[i][j - 1 ]); } } return sum[m - 1 ][n - 1 ]; } }
思路:
state: f[i]表示前i个位置跳到i的方案数
function: f[i] = f[i-1] + f[i-2]
initialize: f[0] = 1, f[1] = 2
answer: f[n-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
public class { public int climbStairs (int n) { int first = 1 ; int second = 2 ; if (n == 1 ) return first; if (n == 2 ) return second; int result = 0 ; for (int i = 2 ; i < n; i++) { result = first + second; first = second; second = result; } return result; } }
思路:
state: f[i]表示前i个位置能否跳到第i个位置
function: f[i] = OR(f[j], 0 < j < i && j能跳到i)
initialize: f[0] = true
answer: f[n-1]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public class { public boolean canJump (int [] nums) { int n = nums.length; boolean [] result = new boolean [n]; result[0 ] = true ; for (int i = 1 ; i < n; i++) { for (int j = 0 ; j < i; j++) { if (result[j] && nums[j] + j >= i) { result[i] = true ; break ; } } } return result[n - 1 ]; } }
近期评论