LeetCode 403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k – 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

LeetCode 91. Decode Ways

思路

• 判断当前的字母s[i]能不能单个decode，如果可以，那方法数就要加上解码s[i-1]时的方法数，如果不能解那就不加；
• 判断两个字符s[i-1]s[i]的组合能不能解码（就是在不在10-26的范围内），如果可以，拿加上解码s[i-2]时的方法数；

LeetCode 64. Minimum Path Sum

思路

$minVal[x][y] = min( minVal[x-1][y], minVal[x][y-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".

LeetCode 62. Unique Paths

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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

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".

LeetCode 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

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

思路

• 尝试使用coin[i]，即当前的最优结果=(X-coins[i])元时的最优结果+1，这个1就是用了coins[i]这个硬币；
• 保持现有结果不变

M\$ 2016 题目3 : Demo Day

描述

You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.

The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.

Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.

While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?

输入

Line 1: N, M.

Line 2-N+1: the N * M maze.

For 20% of the data, N * M <= 16.

For 50% of the data, 1 <= N, M <= 8.

For 100% of the data, 1<= N, M <= 100.

输出

The minimum number of grids to be changed.