leetcode day10 动态规划篇 64+139

64 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

解题思路：动态规划题步骤

dp[i][j]表示到i行j列最小路径和

1、初始化，dp[i][j]=grid[i-1][j-1]

只有一条路径的，即图形左边缘和上边缘，初始化。

 dp[i][1]+=grid[j][0]

  dp[1][i]+=grid[0][j]

3、确定状态转移方程

dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j]

int min(int a,int b){if(a>b)return b;else return a;
}
int minPathSum(int** grid, int gridSize, int* gridColSize) {//m为行，n为列int m=gridSize,n=gridColSize[0];if(m==0||n==0)return 0;int dp[205][205]={};//初始化for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=grid[i-1][j-1];}}for(int i=2;i<=m;i++){for(int j=0;j<i-1;j++){dp[i][1]+=grid[j][0];}}for(int i=2;i<=n;i++){for(int j=0;j<i-1;j++){dp[1][i]+=grid[0][j];}}//确定状态转移方程for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+dp[i][j];}}return dp[m][n];
}

139 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路：动态规划

dp[i]=1表示前i个来自字典,Size[i]为字典中第i个单词的长度

1、初始化 dp[0]=1,其他为0

2、确定状态转移方程

i从1开始，那么k=i-1+Size[j]

dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0)

strcmp与strncmp都是用来比较字符串的，区别在于能否比较指定长度字符串，故要多传一个长度参数。头文件为<string.h>

——举个例子 leetcode 字典为leet code

Size[0]=4,Size[1]=4

i=1,j=0,k=4,dp[4]=dp[0]&&strncmp(s,wordDict[0],Size[0]==0)=1

i=2,j=0,k=5,dp[5]=dp[1]&&strncmp(s+1,wordDict[0],Size[0]==0)=0

……

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[0],Size[0]==0)=0

i=5,j=0,k=8,dp[8]=dp[4]&&strncmp(s+4,wordDict[1],Size[1]==0)=1

所以dp[8]=1=true

思考：如果字典中的单词不能重复使用，该怎么做

可以设个标记flag数组，如果字典第i个单词用过，即dp[k]=1时，标记flag[j]为1。

j循环中，当flag[j]==0时才使用下面的步骤

bool wordBreak(char * s, char ** wordDict, int wordDictSize){int len=strlen(s),i,j;if(wordDictSize==0)return 0;int Size[wordDictSize]={};for(i=0;i<wordDictSize;i++)Size[i]=strlen(wordDict[i]);//dp[i]=1表示前i个来自字典int dp[len+1];dp[0]=1;for(i=1;i<=len;i++)dp[i]=0;for(i=1;i<=len;i++){for(j=0;j<wordDictSize;j++){int k=i-1+Size[j];if(k>len)continue;dp[k]=dp[k]||(dp[i-1]&&strncmp(s+i-1,wordDict[j],Size[j])==0);}}return dp[len];
}